https://vjudge.net/contest/68966#problem/D
http://blog.csdn.net/u010489389/article/details/19218795
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=;
int n;
struct hmwk
{
char ch[maxn];
int d;
int c;
}p[]; struct DP
{
int time;
int reduced;
int fa;
}dp[(<<)]; char s[][]; void Init()
{
for(int i=;i<(<<);i++)
{
dp[i].fa=-;
dp[i].time=;
dp[i].reduced=INF;
}
dp[].reduced=; }
//按字典序增序输出
bool cmp(const hmwk&x,const hmwk& y)
{
return strcmp(x.ch,y.ch)<=;
}
//递归输出，x为当前,fa为前一个
void Print(int x,int fa)
{
int flag;
if(x==)
{
for(int i=;i<n;i++)
{
if(fa&(<<i))
{
flag=i;
break;
}
}
printf("%s\n",p[flag].ch);
return;
}
Print(dp[x].fa,x);
for(int i=;i<n;i++)
{
if((x&(<<i))!=(fa&(<<i)))
{
flag=i;
break;
}
}
if(x==)
{
printf("%s\n",p[flag].ch);
}
else
{
printf("%s\n",p[flag].ch);
}
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{ scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%s%d%d",p[i].ch,&p[i].d,&p[i].c);
}
sort(p,p+n,cmp);
Init();
//每个i代表一个状态，i的每一位代表一个科目
for(int i=;i<(<<n);i++)
{
for(int k=;k<n;k++)
{
//如果是1跳过
if(i&(<<k))
{
continue;
}
//now为转移后的状态
int now=i+(<<k);
dp[now].time=dp[i].time+p[k].c;
//dp[now].time-p[k].d<0说明没有延期，就是0
if(dp[i].reduced+max(,dp[now].time-p[k].d)<dp[now].reduced)
{
dp[now].reduced=dp[i].reduced+max(,dp[now].time-p[k].d);
dp[now].fa=i;
}
}
}
//最终结果就是111111(n个1),对应的数就是(1<<n)-1
printf("%d\n",dp[(<<n)-].reduced);
Print(dp[(<<n)-].fa,(<<n)-);
}
return ;
}