# 状态压缩dp问题

Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework).

Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.

Output
For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.

Sample Input
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3

Sample Output
2
Computer
Math
English
3
Computer
English
Math

/*分析：对于n种家庭作业，全部做完有n!种做的顺序

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;

const int MAX=(1<<15)+10;
int n;
int dp[MAX],t[MAX],pre[MAX],dea[20],fin[20];//dp[i]记录到达状态i扣的最少分,t时相应的花去多少天了
char s[20][110];

void output(int x){
if(!x)return;
output(x-(1<<pre[x]));
printf("%s\n",s[pre[x]]);
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;++i)scanf("%s%d%d",&s[i],&dea[i],&fin[i]);
int bit=1<<n;
for(int i=1;i<bit;++i){//枚举到达状态i
dp[i]=INF;//初始化到达状态i的扣分
for(int j=n-1;j>=0;--j){//由于输入时按字符大小输入，而每次完成j相当于把j放在后面完成且下面判断是dp[i]>dp[i-temp]+score
int temp=1<<j;      //所以是n-1开始，如果下面判断是dp[i]>=dp[i-temp]+score则从0开始
if(!(i&temp))continue;//状态i不存在作业j完成则不能通过完成作业j到达状态i
int score=t[i-temp]+fin[j]-dea[j];//i-temp表示没有完成j的那个状态
if(score<0)score=0;//完成j被扣分数最小是0
if(dp[i]>dp[i-temp]+score){
dp[i]=dp[i-temp]+score;
t[i]=t[i-temp]+fin[j];//到达状态i花费的时间
pre[i]=j;//到达状态i的前驱,为了最后输出完成作业的顺序
}
}
}
printf("%d\n",dp[bit-1]);
output(bit-1);//输出完成作业的顺序
}
return 0;
}