hdu 1074 Doing Homework 状态压缩DP

题意：给出n个作业的名称，死线，用时，每个课程每超过死线一天扣一分，求最小扣分及其排列，多种情况下输出字典序最小的一组。

由于n最大只有15，所以用状态压缩，从1到1<<n遍历，若该状态下包含课程j已完成（i&1<<j==1)并且当前完成j的分数最少，更新该状态。

最后输出(1<<n)-1的分数，dfs输出课程。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 1<<16
#define INF 0x7fffffff

using namespace std;

struct node
{
    string s;
    int d,c;
}a[30];

struct node1
{
    int time,pre,now,point;
}d[N];

void dfs(int t)
{
    if(t==0) return;
    dfs(d[t].pre);
    cout<<a[d[t].now].s<<endl;
}

int main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i].s>>a[i].d>>a[i].c;
        int m=1<<n;
        memset(d,0,sizeof(d));
        for(int i=1;i<m;i++)
        {
            d[i].point=INF;
            for(int j=n-1;j>=0;j--)
            {
                int t=1<<j;
                if(t&i)
                {
                    int past=i-t;
                    int cost=max(0,d[past].time+a[j].c-a[j].d);
                    if(cost+d[past].point<d[i].point)
                    {
                        d[i].point=d[past].point+cost;
                        d[i].now=j;
                        d[i].pre=past;
                        d[i].time=d[past].time+a[j].c;
                    }
                }
            }
        }
        cout<<d[m-1].point<<endl;
        dfs(m-1);
    }
}