题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074
题目大意：T个 test case。对于每个test case，有N门课的作业，对于每门课的作业，对应一个期限D和完成所需时间C。如果没有在期限D之前完成作业，那么每过一天扣一分，问怎么安排做作业的顺序才能使扣分最少。注意，1<=N<=15。
解题思路：
由于1<=N<=15，可以使用状态压缩DP。用 dp[i] 中的 i 记录已完成的作业，（例，i = 18 = 10010，代表其第2，5门作业已完成，而其他的则未完成，因为左数第2，5位上的数字为1）。
状态转移方程：以 i 为外循环，在内循环遍历所有作业，对于一个 i ，如果第 j 门作业已经完成，那么不考虑，如果未完成，那么 dp[i|(1<<j)] = min( dp[i|(1<<j)], dp[i] + cal() ). cal()是一个用于计算加上这一门课程后要扣多少分的函数。
仍然用 vector<int> path[ ] 记录路径。由于在给出课名的时候本身就是按照字典序排列的，而且我们的遍历顺序也是从 0 开始，所以对于里面的什么升序排列不用考虑。
waring: 移位符号的优先级极低，所以很多时候都要加（），不然会出bug。
1 #include <cstdio> 2 #include <vector> 3 using namespace std; 4 const int maxn=1<<16; 5 const int inf=0x7ffffff; 6 vector<int> path[maxn]; 7 int dp[maxn]; 8 struct classes{ 9 char name[110]; 10 int D,C; 11 }cs[20]; 12 int cal(int d,int ed){ 13 if(ed<=d) return 0; 14 return ed-d; 15 } 16 int main(){ 17 int T,N; 18 scanf("%d",&T); 19 while(T--){ 20 scanf("%d",&N); 21 for(int i=0;i<N;i++){ 22 scanf("%s",cs[i].name); 23 scanf("%d%d",&cs[i].D,&cs[i].C); 24 } 25 for(int i=0;i<(1<<N);i++){ 26 dp[i]=inf; 27 path[i].clear(); 28 } 29 dp[0]=0; 30 int days; 31 for(int i=0;i<(1<<N);i++){ //注意括号 32 days=0; 33 for(int j=0;j<N;j++){ 34 if((1<<j)&i) //括号 35 days+=cs[j].C; 36 } 37 for(int j=0;j<N;j++){ 38 if((i&(1<<j))==0){ //i&(1<<j)外面一定要加括号 39 int ca=cal(cs[j].D,days+cs[j].C); 40 if(dp[i|(1<<j)]>dp[i]+ca){ 41 path[i|(1<<j)]=path[i]; 42 path[i|(1<<j)].push_back(j); 43 dp[i|(1<<j)]=dp[i]+ca; 44 } 45 } 46 } 47 } 48 printf("%d ",dp[(1<<N)-1]); 49 for(int i=0;i<path[(1<<N)-1].size();i++){ 50 int ind=path[(1<<N)-1][i]; 51 printf("%s ",cs[ind].name); 52 } 53 } 54 return 0; 55 }