之前做过一个题,是在学贪心的时候做的,所以这个题就想当然的跑偏了,当看到N是<=16 的时候,状态压缩就理所当然了
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define INF 0x3f3f3f3f struct Dp { int reduce; int tim; int fa; }; struct Course { int d; int c; char name[110]; }; Dp dp[1<<16]; Course cla[16]; void print(int num) { if(num <= 0) return; int temp,id = 0; print(dp[num].fa); temp = dp[num].fa ^ num; while(! (temp & 1) ) { id++; temp >>= 1; } printf("%s\n",cla[id].name); } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i = 0;i < n;i++) scanf("%s%d%d",cla[i].name,&cla[i].d,&cla[i].c); for(int i = 0;i < 1<<n;i++) { if(i == 0) dp[i].reduce = 0; else dp[i].reduce = INF; dp[i].tim = 0; dp[i].fa = -1; for(int j = 0;j < n;j++) { int temp = 1<<j; if(temp & i) { dp[i].tim = dp[i^temp].tim + cla[j].c; int reduces = dp[i].tim - cla[j].d; if(reduces < 0) reduces = 0; if(dp[i].reduce >= dp[i^temp].reduce + reduces) { dp[i].fa = i^temp; dp[i].reduce = dp[i^temp].reduce + reduces; } } } } printf("%d\n",dp[(1<<n)-1].reduce); print((1<<n)-1); } return 0; }
原文：http://www.cnblogs.com/jifahu/p/5449601.html