题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))#define pii pair<ll,ll>
#define mk(x,y) make_pair(x,y)const int maxn =20;
const int mod=998244353;
const int inf=1e9+7;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：有若干个作业，给定截止日期和完成所需时间，
每次超出截止日期一天就累加权重1，问完成所有作业的权重最小值。典型的状压DP，
状压DP的一个关建是状态如何进行转移，
从最小的状态去铺垫后面的状态，
这题有个很关键的贪心就是，
不难发现把任务连在一起做最优，
就是中间无空隙，
这样就好办了，对于状压DP数组，
记录结构体，包含上一个状态，最优值，和当前状态所花的时间。
如此进行转移，套一下状压的套路就行了。*/
int n;
struct node{char name[maxn*10];int deadtime,dur;///该任务的截止时间和完成所需要的时间
}task[maxn];///任务节点数组struct Dp{int cur;///当前的任务int v;///当前的权值int t;///当前的时间
}dp[1<<17];///dp数组void output(int S){///回溯输出答案if(S==0)return ;int idx=dp[S].cur;///回溯的关键是根据dp数组的状态信息~output(S^(1<<idx));printf("%s\n",task[dp[S].cur].name);
}int main(){int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%s%d%d",task[i].name,&task[i].deadtime,&task[i].dur);for(int i=0;i<(1<<n);i++)dp[i].v=inf;///先把状态数组全部标记为不可用状态dp[0].v=0;///0状态是可用的for(int i=0;i<(1<<n);i++){ ///先遍历所有状态if(dp[i].v==inf) continue;///只选取有用的状态节点进行更新for(int j=0;j<n;j++){ ///注意，最好下标从0开始int tmp=(1<<j);if(i&tmp) continue;///如果当前的状态已经包含了搜索到的任务，直接跳过~tmp|=i;int val=(dp[i].t+task[j].dur-task[j].deadtime);val=max(val,0);///如果不超出当前时间则无影响if(dp[tmp].v>dp[i].v+ val){dp[tmp].v=dp[i].v+ val;///更新状态数组dp[tmp].cur=j;///当前任务换成jdp[tmp].t=dp[i].t+task[j].dur;///更新状态数组当前的时间}}}printf("%d\n",dp[(1<<n)-1].v);output((1<<n)-1);///利用状态回溯输出路径}return 0;
}