用10表示每门作业的完成情况，然后暴力转移状态即可。
/* 11111111 00000110 00001100 00011000 00110000 01100000 */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<map> #include<queue> #include<vector> #define ll long long #define debug(x); printf("debug%d ",x); using namespace std; const int inf=0x3f3f3f3f; int T,n; int name[20][105]; int dead[20]; int need[20]; const int N=32780; int dp[N];//达到状态i所扣的分。 int t[N];//达到状态i的时间. int pre[N];//寻找前继. void outp(int x) { if(!x) return; outp(x-(1<<pre[x])); printf("%s ",name[pre[x]]); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); memset(t,0,sizeof t); for(int i=0;i<n;i++) { scanf("%s%d%d",&name[i],&dead[i],&need[i]); } int hehe=1<<n; for(int i=1;i<hehe;i++) { dp[i]=inf;//达到状态i的扣分. for(int j=n-1;j>=0;j--) { int temp=1<<j; if(!(i&temp)) continue; int score=t[i-temp]+need[j]-dead[j]; if(score<0) score=0; if(dp[i]>dp[i-temp]+score) { dp[i]=dp[i-temp]+score; pre[i]=j; t[i]=t[i-temp]+need[j]; } } } printf("%d ",dp[hehe-1]); outp(hehe-1); } }