考虑到n只有15，那么状压DP即可。
题目要求说输出字典序最小的答案的顺序，又考虑到题目给出的字符串本身字典序是递增的，那么枚举i的时候倒着来即可。因为在同样完成的情况下，后选字典序大的，小的字典序就会在前面，那么整体的字典序就会更小。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <string> 5 #include <iostream> 6 #include <stack> 7 using namespace std; 8 const int inf = 0x3f3f3f3f; 9 10 struct node 11 { 12 string name; 13 int cost,deadline; 14 }a[20]; 15 struct state 16 { 17 int pre,now; 18 int t,score; 19 }dp[1<<16]; 20 21 int main() 22 { 23 int T; 24 scanf("%d",&T); 25 while(T--) 26 { 27 int n; 28 scanf("%d",&n); 29 for(int i=0;i<n;i++) cin >> a[i].name >> a[i].deadline >> a[i].cost; 30 int all = 1 << n; 31 for(int mask=1;mask<all;mask++) 32 { 33 dp[mask].score = inf; 34 for(int i=n-1;i>=0;i--) 35 { 36 if(mask & (1<<i)) 37 { 38 int pre = mask - (1<<i); 39 int add = dp[pre].t + a[i].cost - a[i].deadline; 40 if(add < 0) add = 0; 41 if(dp[pre].score + add < dp[mask].score) 42 { 43 dp[mask].score = dp[pre].score + add; 44 dp[mask].pre = pre; 45 dp[mask].now = i; 46 dp[mask].t = dp[pre].t + a[i].cost; 47 } 48 } 49 } 50 } 51 int temp = all - 1; 52 printf("%d ",dp[temp].score); 53 stack<int> S; 54 while(temp) 55 { 56 S.push(dp[temp].now); 57 temp = dp[temp].pre; 58 } 59 while(!S.empty()) 60 { 61 int x = S.top(); S.pop(); 62 cout << a[x].name << endl; 63 } 64 } 65 return 0; 66 }