由于数据量较小，直接二进制模拟全排列过程，进行DP，思路由kuangbin blog得到，膜拜斌神
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> using namespace std; struct asd { char name[105]; int deadline,cost; } o[18]; struct cc { int pre; int cost; int reduced; } dp[1<<16]; bool vis[1<<16]; int tt; void output(int now) { int cur=(dp[now].pre^now); cur>>=1; int c=0; while(cur) { ++c; cur>>=1; } if(dp[now].pre!=0) output(dp[now].pre); printf("%s ",o[c].name); } int main() { int n,T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0; i<n; ++i) scanf("%s%d%d",o[i].name,&o[i].deadline,&o[i].cost); dp[0].cost=0; dp[0].reduced=0; dp[0].pre=-1; memset(vis,0,sizeof(vis)); vis[0]=1; tt=(1<<n)-1; for(int i=0; i<tt; ++i) { for(int j=0; j<n; ++j) { if((i&(1<<j))==0) { int cur=(i|(1<<j)); if(vis[cur]) { int more=dp[cur].cost-o[j].deadline; more=max(0,more)+dp[i].reduced; if(more<dp[cur].reduced) dp[cur].pre=i,dp[cur].reduced=more; } else { dp[cur].pre=i; dp[cur].cost=dp[i].cost+o[j].cost; int more=dp[cur].cost-o[j].deadline; dp[cur].reduced=dp[i].reduced+max(more,0); vis[cur]=1; } } } } printf("%d ",dp[tt].reduced); output(tt); } return