题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074
题意：n个作业，截止时间di，需要ci时间做完，每超过截止时间一天罚一分，问最少罚多少分。
1<=N<=15，状态压缩。
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=16; 4 int dp[1<<maxn],t[1<<maxn],pre[1<<maxn]; 5 int d[maxn],c[maxn]; 6 char s[maxn][120]; 7 int n; 8 void print(int x) 9 { 10 if(x==0) return ; 11 print(pre[x]); 12 x-=pre[x]; 13 for(int i=0;i<n;i++) 14 if(x&1<<i) puts(s[i]); 15 } 16 int main() 17 { 18 int tt; 19 scanf("%d",&tt); 20 while(tt--) 21 { 22 int cost; 23 scanf("%d",&n); 24 memset(dp,0x3f,sizeof(dp)); //之前还没这么用过，一直以为只能赋0和1 25 for(int i=0;i<n;i++) 26 scanf("%s%d%d",s[i],&d[i],&c[i]); 27 dp[0]=t[0]=0; //初始罚分为0； 28 int m=1<<n; 29 for(int i=1;i<m;i++) //枚举所有补过的作业状态，1为补过，0为未补 30 for(int j=0;j<n;j++) //按位寻找合法前驱 31 { 32 if((i&1<<j)==0) continue; 33 int k=i-(1<<j); //k是前驱状态 34 t[i]=t[k]+c[j]; //从状态k到i（这次做j号作业），到此一共耗时为t[k]+c[j] 35 cost=t[i]-d[j]>0?t[i]-d[j]:0; //计算罚分 36 if(dp[i]>=dp[k]+cost) // 用>=是为了最小字典序 37 { 38 dp[i]=dp[k]+cost; 39 pre[i]=k; //记录前驱状态 40 } 41 } 42 printf("%d ",dp[m-1]); 43 print(m-1); //递归打印 44 } 45 }