考虑到n只有15，那么状压DP即可。
题目要求说输出字典序最小的答案的顺序，又考虑到题目给出的字符串本身字典序是递增的，那么枚举i的时候倒着来即可。因为在同样完成的情况下，后选字典序大的，小的字典序就会在前面，那么整体的字典序就会更小。代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
using namespace std;
const int inf = 0x3f3f3f3f; struct node
{
string name;
int cost,deadline;
}a[];
struct state
{
int pre,now;
int t,score;
}dp[<<]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=;i<n;i++) cin >> a[i].name >> a[i].deadline >> a[i].cost;
int all = << n;
for(int mask=;mask<all;mask++)
{
dp[mask].score = inf;
for(int i=n-;i>=;i--)
{
if(mask & (<<i))
{
int pre = mask - (<<i);
int add = dp[pre].t + a[i].cost - a[i].deadline;
if(add < ) add = ;
if(dp[pre].score + add < dp[mask].score)
{
dp[mask].score = dp[pre].score + add;
dp[mask].pre = pre;
dp[mask].now = i;
dp[mask].t = dp[pre].t + a[i].cost;
}
}
}
}
int temp = all - ;
printf("%d\n",dp[temp].score);
stack<int> S;
while(temp)
{
S.push(dp[temp].now);
temp = dp[temp].pre;
}
while(!S.empty())
{
int x = S.top(); S.pop();
cout << a[x].name << endl;
}
}
return ;
}