HDU 1074（dp46）（状态压缩dp）

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int INF=0x3f3f3f3f; struct node1 { string name; int deadline; int cost; }homework[20]; struct node2 { int now; int pre; int time; int score; }dp[1<<15]; int main() { int T; scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); int i,j,k; int n; scanf("%d",&n); for(i=0;i<n;i++) { cin>>homework[i].name>>homework[i].deadline>>homework[i].cost; } int end=1<<n; for(i=0;i<=end-1;i++) { dp[i].score=INF; dp[0].score=0; for(j=n-1;j>=0;j--) { int tmp=1<<j; if(tmp&i) { int past=i-tmp; int temp=dp[past].time+homework[j].cost-homework[j].deadline; if(temp<0) { temp=0; } if(temp+dp[past].score<dp[i].score) { dp[i].now=j; dp[i].pre=past; dp[i].time=dp[past].time+homework[j].cost; dp[i].score=temp+dp[past].score; } } } } stack<int> S; end-=1; cout<<dp[end].score<<endl; while(end) { S.push(dp[end].now); end=dp[end].pre; } while(!S.empty()) { cout<<homework[S.top()].name<<endl; S.pop(); } } return 0; }