HDU 1074

DP类的状态压缩。这题其实就是求所有家庭作业的全排列，也就是最多有15！种放法，而 15！=1 307 674 368 00 所以暴力肯定会超时的。
这题的模型就是类似于数塔一样的。同时由于状态太多。所以利用二进制状态压缩。

下面是AC代码 ：
[cpp] 
#include<iostream> 
#include<string> 
#include<stack> 
using namespace std; 
struct node{ 
    string name;            
    int d;                                  //截止日期 
    int c;                                  //需要花费日期  
}hw[20]; 
 
struct point{ 
    int now,pre;                           //当前状态id,与过去状态id 
    int now_time;                          //当前时间 
    int score;                             //当前最少花费 
    int key;                               //当前课程的id 
     
}dp[40000]; 
int main(){ 
    int t,n,i,j; 
     
    cin>>t; 
     
    while(t--){ 
        cin>>n; 
        for(i=0;i<n;i++)  cin>>hw[i].name>>hw[i].d>>hw[i].c; 
         
        dp[0].now_time=0;  dp[0].score=0;   dp[0].now=0; 
         
        for(i=1;i<(1<<(n));i++){ 
            dp[i].score=1000000000; 
            for(j=n-1;j>=0;j--){ 
                if(i&(1<<j)){ 
                    int pre_id=i-(1<<j),temp=0; 
                     
                    if(dp[pre_id].now_time+hw[j].c>hw[j].d) 
                        temp=dp[pre_id].now_time+hw[j].c-hw[j].d; 
                    else temp=0; 
                     
                     
                    if(dp[pre_id].score+temp<dp[i].score){ 
                        dp[i].score=dp[pre_id].score+temp; 
                        dp[i].now=i; 
                        dp[i].pre=pre_id; 
                        dp[i].now_time = dp[pre_id].now_time+hw[j].c; 
                        dp[i].key=j; 
                         
                    } 
                } 
            } 
             
        } 
         
         
        stack<string >st; 
        cout<<dp[(1<<n)-1].score<<endl; 
         
        int t=(1<<(n))-1; 
         
        while(dp[t].now!=0){ 
             
            st.push(hw[dp[t].key].name); 
            t=dp[t].pre; 
        //  cout<<t<<endl; 
             
        } 
        while(!st.empty()){ 
            cout<<st.top()<<endl; 
            st.pop(); 
        } 
         
         
    } 
    return 0; 
}