Hdoj-1074-状压dp

n个课程就是一个有n位置的二进制数，然后从0(也就是还没写作业)到(1<< n)-1(也就是全写完DP求最优解)
比如说 要完成四门作业的话此时要推dp[1011]（第1，2，4门作业完成最少扣得分）那它就是由 dp[1001],dp[0011],dp[1010]三个状态转移的最优解，
置于顺序输出则先由0011转移再由1001转移再由1010转移（物品从n-1到0进行选取也就是先把下表大的作业去掉）

#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
struct node{
   int time,score,past;
}dp[1<<20];
struct cl{
   int  li,fin;
    string name;
}a[100];
int n;
int main()
{
    int t;
    scanf("%d",&t);
   while(t--)
   {
         scanf("%d",&n);
         for(int i=0;i<n;i++)
           cin>>a[i].name>>a[i].li>>a[i].fin;
         int n1 = (1<<n)-1;
         dp[0].time = 0;
         dp[0].score = 0;
         dp[0].past = 0;
         for(int i=1;i<=n1;i++)//DP
       {
               dp[i].score = 0x7ffffff;
                 for(int j=n-1;j>=0;j--)//保证顺序输出
                 {
                      if(i&(1<<j)){
                              int past = i-(1<<j);
                                int ans = dp[past].time+a[j].fin-a[j].li;
                                int ma = ans>0?  ans:0;
                                if(dp[past].score+ma<dp[i].score){
                                     dp[i].score = dp[past].score + ma;
                                     dp[i].past = past;
                                     dp[i].time = dp[past].time+a[j].fin;
                                }
                        }   
                 }
         }
         printf("%d\n",dp[n1].score);
         stack<int>st;
         int pre = n1;
         while(pre)
         {
              st.push(pre-dp[pre].past);
              pre = dp[pre].past;
         }
         while(!st.empty())
         {
               int ans = st.top(),i1 = 0;
               st.pop();
                 while(ans){
                     i1++;
                     ans>>=1;
                 }
               cout<<a[i1-1].name<<endl;
         }
     }
  return 0;
}