题意：有各种作业，分别给出用时，最后期限，每超一天就扣一分。问做完所有作业的最少扣分及其策略。
Analyse：自己看的时候是一头雾水，看别人的题解上写的是状态压缩的DP。状态压缩：用0和1表示某一作业的状态，1代表已完成，0代表未动手，一个int足以表示所有的不同状态，例如5中的5表示为二进制就是101，代表第一个作业和第三个作业已经完成，第二个作业未完成，dp[5]就表示假设只有三个作业，只完成第一和第三个作业扣的最少分数。
View Code
1 #include<string> 2 #include<iostream> 3 #include<vector> 4 using namespace std; 5 #define INF 0xfffffff 6 typedef struct 7 { 8 int used_days;//用掉的时间 9 int preseq;//这个序列之前的序列 10 int thiswork; 11 int deducted;//扣除的分数 12 }sequence; 13 typedef struct 14 { 15 string title;//科目名 16 int cost;//完成作业花费的时间 17 int deadline;//最后期限 18 }subject; 19 sequence seq[1024*1024]; 20 subject sub[16]; 21 vector<int> list; 22 int main() 23 { 24 int t,n; 25 int i,j,max; 26 int temp,deducted,last; 27 cin>>t;; 28 while(t--) 29 { 30 cin>>n; 31 for(i=0;i<n;i++) 32 cin>>sub[i].title>>sub[i].deadline>>sub[i].cost; 33 max=1<<n; 34 seq[0].used_days=0; 35 seq[0].preseq=-1; 36 seq[0].deducted=0; 37 for(i=1;i<max;i++) 38 { 39 seq[i].deducted=INF; 40 for(j=n-1;j>=0;j--) 41 { 42 temp=1<<j; 43 if(i&temp) 44 { 45 last=i-temp; 46 deducted=seq[last].used_days+sub[j].cost-sub[j].deadline; 47 if(deducted<0) 48 deducted=0; 49 if(seq[last].deducted+deducted<seq[i].deducted) 50 { 51 seq[i].deducted=seq[last].deducted+deducted; 52 seq[i].preseq=last; 53 seq[i].used_days=seq[last].used_days+sub[j].cost; 54 seq[i].thiswork=j; 55 } 56 } 57 } 58 } 59 cout<<seq[max-1].deducted<<endl; 60 for(i=max-1;i!=0;i=seq[i].preseq) 61 list.push_back(seq[i].thiswork); 62 for(i=list.size()-1;i>=0;i--) 63 cout<<sub[list[i]].title<<endl; 64 list.clear(); 65 } 66 return 0; 67 }
后话：/*后来的专题训练再把这道题做一次，科目输出的顺序总是搞不对，问题在于没注意中间的for是逆序循环的，逆序才能保证最终的顺序是字典序。因为逆序时优先考虑字典序小的先完成。*/