HDU1074 Doing Homework（状压dp）

题意：给定有n门课的作业，每门课交作业有截止时间，和完成作业所花费的时间，如果超过规定时间完成，每超过一天就会扣1分，求一个做作业顺序要求扣的分数最少。

思路：因为数据最大是15，可以使用二进制来表示所有完成的状况，比如二进制位1001，代表第1和第4科目的作业完成，第2第3没有完成，那么从0到（1<<n）其二进制就是所有的状态了。首先枚举所有的状态，然后枚举每一门课，假如判断第i门课是否完成可以用1<< i & （当前状态）来判断，然后去更新上次的状态+上完这门课完成所花费的最小分数，dp记录状态路径，最后输出即可。

AC代码：

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<queue>
 7 #include<cstdio>
 8 #include<stack>
 9 #include<unordered_map>
10 #define inf 0x3f3f3f3f
11 using namespace std;
12 typedef long long ll;
13 const int maxn = (1<<15)+5;
14 struct node{
15     string name;
16     int end;
17     int cost;
18 }g[35];
19 struct node1{
20     int time;
21     int val;
22     int last;
23     int cur;
24 }dp[maxn];
25 int m,n; 
26 int main(){
27     int t;
28     cin>>t;
29     while(t--){
30         int n;
31         scanf("%d",&n);
32         memset(dp,0,sizeof(dp));
33         for(int i = 1;i<=n;i++) {
34             cin>>g[i].name ;
35             cin>>g[i].end>>g[i].cost; 
36         }
37         int up = 1<<n;
38         for(int i = 1;i<up;i++){
39             dp[i].val = 1<<30;//设置花费的最大值 
40             for(int j = n;j>=1;j--){
41                 int temp = 1<<(j-1);//枚举第j门课是否完成 
42                 if(i & temp){//如果完成 
43                     int last = i - temp;//last为完成第j门课作业之前的状态 
44                     int s = dp[last].time + g[j].cost - g[j].end ;//完成第j门课所需要的花费 
45                     if(s<0) s = 0;
46                     if(dp[last].val + s <dp[i].val ){//如果扣分少于当前的i状态，则进行更新 
47                         dp[i].cur = j; //i状态最后完成的科目是j 
48                         dp[i].val = dp[last].val + s;//更新到i状态扣的分数 
49                         dp[i].time = dp[last].time + g[j].cost;//i更新到i状态的最小时间 
50                         dp[i].last = last; //i状态的上一个状态进行更新 
51                     } 
52                 }
53             }
54         }
55         stack<int> s;
56         int temp = up - 1;
57         printf("%d
",dp[temp].val);//up-1为完成的状态 
58         while(temp){
59             s.push(dp[temp].cur);//把路径依次读入栈中 
60             temp = dp[temp].last;
61         }
62         while(!s.empty()){
63             cout<<g[s.top()].name<<endl;
64             s.pop();
65         } 
66     }
67     return 0;
68 }