典型的状态压缩DP，给出了每件作业的截止时间和花费，求让老师扣分最少的写作业方式。把完成n种作业用状态2^n-1表示，dp[s]表示
完成状态s时，最小扣分。比如“111”，那么可以由“011”，“110”，“101”转移过来，分别表示选了0，1号作业，1，2号作业，0，2号作业。
t【s】表示状态S记录的总时间。dp[s] = min{dp[j]+c[k] - d[k]},其中j = i^(1<<k),0<k<n;pre【s】表示状态s完成时，最末尾完成的作业，
#include<cstdio> #include<iostream> #include<climits> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #define INF INT_MAX using namespace std; typedef long long ll; const int maxn = 100; char w[20][150]; int d[20],c[20]; int dp[1<<15]; int t[1<<15]; int pre[1<<15]; void print(int st) { if(st == 0) return ; int x = pre[st]; st = st-(1<<x); print(st); printf("%s ",w[x]); } int main() { freopen("in","r",stdin); int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); getchar(); for(int i = 0; i < n; ++i) { scanf("%s%d%d",w[i],d+i,c+i); getchar(); } //printf("^^^ "); for(int i = 1; i <= (1<<n)-1; ++i) { dp[i] = INF; for(int k = 0; k < n; ++k) { if((i&(1<<k)) != 0) { int j = i-(1<<k); int score = t[j] + c[k]-d[k]; if(score < 0) score = 0; if(dp[j] + score <= dp[i])//由于dp的方向是从0-2^n-1递推的，所以当出现dp值相同的状态时应该选K大的放在末尾。这样，K小的还可以在前面的决策中再选。。 { dp[i] = dp[j] + score; t[i] = t[j]+c[k]; pre[i] = k; printf("%d %d ",i,pre[i]); } } } } printf("%d ",dp[(1<<n)-1]); print((1<<n)-1); memset(t,0,sizeof(t)); memset(pre,0,sizeof(pre)); memset(dp,0,sizeof(dp)); } }