题目 ： 给一些不同科目作业（至多15）的完成所需时间和截止时间，每当超过完成时间1天，就会扣一分，求扣分最少的完成顺序及所扣分数；
Sample Input 2 3 Computer 3 3 English 20 1 Math 3 2 3 Computer 3 3 English 6 3 Math 6 3 Sample Output 2 Computer Math English 3 Computer English Math
并不知道什么是状压dp（挠头，刚开始按dead-cost算了一下，果然不对
看过解答，仍不知什么是状压dp，发现这道题的dp状态描述是按二进制法子集枚举描述的
因为每时刻的一种静止状态都可以用每种科目 做或没做 这两种状态描述，而情况至多有2^15种，dp所占空间并不会太大
所以状态用二进制法描述，状态的转移方向是上一步的状态，以二进制的扫描实现
转移方程 dp【选择此步做了某种作业的某种状态 i】=min（ dp【做该种作业之前的状态 i-1】+【i】扣的分数，dp【i】）；
因为是向前转移，所以填充方向从始态开始
#include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; struct sub{ string name; int dead,cost; }a[20]; struct dp_s{ int id,fa; int goal; int time; }dp[1<<16]; int main(){ int m,n; scanf("%d",&m); while(m--){ memset(dp,0,sizeof(dp)); scanf("%d",&n); for(int i=0;i<n;i++){ cin>>a[i].name>>a[i].dead>>a[i].cost; } int end=1<<n; for(int i=1;i<end;i++){ dp[i].goal=INF; for(int j=n-1;j>=0;j--){ //从 填充的是最靠后位开始扫描 保证输出的字典序 int cur=1<<j; if(i&cur){ //二进制扫描 int tem=i-cur; int time=dp[tem].time+a[j].cost; int goal=time-a[j].dead; if(goal<0)goal=0; goal+=dp[tem].goal; if(goal<dp[i].goal){ dp[i].goal=goal; dp[i].time=time; dp[i].id=j; dp[i].fa=tem; } } } } vector <int> ans; end-=1; printf("%d ",dp[end].goal); while(end)ans.push_back(dp[end].id),end=dp[end].fa; for(int i=ans.size()-1;i>=0;i--)cout<<a[ans[i]].name<<endl; } return 0; }