HDU1074 Doing Homework（状压dp）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074

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

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

AC代码：

 #include<iostream>

 #include<vector>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<queue>

 #include<cstdio>

 #include<stack>

 #include<unordered_map>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long ll;

 const int maxn = (<<)+;

 struct node{

     string name;

     int end;

     int cost;

 }g[];

 struct node1{

     int time;

     int val;

     int last;

     int cur;

 }dp[maxn];

 int m,n;

 int main(){

     int t;

     cin>>t;

     while(t--){

         int n;

         scanf("%d",&n);

         memset(dp,,sizeof(dp));

         for(int i = ;i<=n;i++) {

             cin>>g[i].name ;

             cin>>g[i].end>>g[i].cost;

         }

         int up = <<n;

         for(int i = ;i<up;i++){

             dp[i].val = <<;//设置花费的最大值

             for(int j = n;j>=;j--){

                 int temp = <<(j-);//枚举第j门课是否完成

                 if(i & temp){//如果完成

                     int last = i - temp;//last为完成第j门课作业之前的状态

                     int s = dp[last].time + g[j].cost - g[j].end ;//完成第j门课所需要的花费

                     if(s<) s = ;

                     if(dp[last].val + s <dp[i].val ){//如果扣分少于当前的i状态，则进行更新

                         dp[i].cur = j; //i状态最后完成的科目是j

                         dp[i].val = dp[last].val + s;//更新到i状态扣的分数

                         dp[i].time = dp[last].time + g[j].cost;//i更新到i状态的最小时间

                         dp[i].last = last; //i状态的上一个状态进行更新

                     }

                 }

             }

         }

         stack<int> s;

         int temp = up - ;

         printf("%d\n",dp[temp].val);//up-1为完成的状态

         while(temp){

             s.push(dp[temp].cur);//把路径依次读入栈中

             temp = dp[temp].last;

         }

         while(!s.empty()){

             cout<<g[s.top()].name<<endl;

             s.pop();

         }

     }

     return ;

 }