题意：
小明有n个作业，没个作业有ddl，有完成需要的时间t，一个作业如果超过ddl一个时间，就扣去一分，问最后做完所有作业扣去的分数最少是多少，并输出做作业的顺序。
解题思路：
基础dp题，以为应该很easy，xjb贪了3发，发现不对。
其实很容易想到作业，只不过觉得有点麻烦。
但是想到去写状压了，也就简单了。
用一个1<<15的数的二进制表示当前以及做了哪几项作业。
dp[i][j],i表示第几天，j就是上面的二进制数，
转移就是dp[i+1][j+(1<<k)]=min(dp[i+1][j+(1<<k)], dp[i][j]+a[k].t+t-a[k].d).a[k].t是第k项作业所需时间,a[k].d是ddl。
第一维貌似不需要，但是这样好理解一些。
再用一个pre记录前缀状态就好了。
代码：
#include <bits/stdc++.h> using namespace std; const int inf=1e9+7; struct node { int t; int r; }dp[16][1<<16]; struct contest { char name[105]; int d; int t; }a[105]; int pre[1<<16]; int pos(int x) { for(int i=0; i<16; i++)if((1<<i)&x)return i; } int count(int x) { int res=0; while(x>0) { res+=(x&1); x>>=1; } return res; } int main() { int i, j, t, n, e; cin>>t; while(t--) { scanf("%d", &n); for(i=0; i<=n; i++) { for(j=0; j<=(1<<n); j++) { dp[i][j].r=(i==0)?0:inf; dp[i][j].t=0; } } for(i=0; i<n; i++) { scanf("%s%d%d", a[i].name, &a[i].d, &a[i].t); } int k, l; for(i=0; i<=n; i++) { for(j=0; j<(1<<n); j++) { if(count(j)==i) { for(k=0; k<n; k++) //kaoshi num { if(1<<k & j)continue; l=j+(1<<k); if(dp[i+1][l].r>dp[i][j].r+max(0, dp[i][j].t+a[k].t-a[k].d)) { dp[i+1][l].r=dp[i][j].r+max(0, dp[i][j].t+a[k].t-a[k].d); dp[i+1][l].t=dp[i][j].t+a[k].t; pre[l]=j; // printf("%d %d %d %d %d\n", i, k, l, dp[i+1][l].r); } } } } } int ans[20]; i=0; printf("%d\n", dp[n][(1<<n)-1].r); int x=(1<<n)-1; while(x!=0) { ans[i++]=pos(x-pre[x]); x=pre[x]; } for(i=n-1; i>=0; i--)printf("%s\n", a[ans[i]].name); } }