Doing Homework

有n个任务，每个任务有一个截止时间，超过截止时间一天，要扣一个分。
求如何安排任务，使得扣的分数最少。Input有多组测试数据。第一行一个整数表示测试数据的组数
第一行一个整数n(1<=n<=15)
接下来n行，每行一个字符串(长度不超过100)表示任务的名称和两个整数，分别表示任务的截止时间和完成任务需要的天数。这n个任务是按照字符串的字典序从小到大给出。 Output每组测试数据，输出最少扣的分数的。并输出一个完成任务的方案，如果有多个方案，输出字典序最小的一个。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 struct node{
 7     int sumT;
 8     int val;
 9     int pre;
10 };
11 node dp[(1<<15)];
12 const int INF = 1e9;
13 const int MAX = 20;
14 int ddls[MAX];
15 int Ts[MAX];
16 char names[MAX][100];
17 int order[16];
18 int calc(int x){
19     int cnt = 0;
20     while(x){
21         cnt++;
22         x >>= 1;
23     }
24     return cnt-1;
25 }
26 int main(){
27     int T;scanf("%d",&T);
28     while(T--){
29         for(int i = 0;i < (1<<15);i++){
30             dp[i].val = INF;
31         }
32         int n;
33         scanf("%d",&n);
34         for(int i = 0;i < n;i++){
35             scanf("%s %d%d",names[i],&ddls[i],&Ts[i]);
36         }
37         dp[0].pre = 0;
38         dp[0].sumT = 0;
39         dp[0].val = 0;
40         for(int S = 0;S < (1<<n);S++){
41             for(int i = 0;i < n;i++){
42                 if((S & (1<<i)) == 0){
43                     int tar = S|(1<<i);
44                     int cost = 0;
45                     if(dp[S].sumT + Ts[i] > ddls[i])
46                         cost = dp[S].sumT + Ts[i] - ddls[i];
47                     if(dp[tar].val > dp[S].val + cost ){
48                         dp[tar].val = dp[S].val + cost;
49                         dp[tar].sumT = dp[S].sumT + Ts[i];
50                         dp[tar].pre = S;
51                     }
52                 }
53             }
54         }
55         cout<<dp[(1<<n)-1].val<<endl;
56         int S = (1<<n)-1;
57         int cnt = n;
58         while(S){
59             int nS = dp[S].pre;
60             int t = calc(nS ^ S);
61             order[--cnt] = t;
62             S = nS;
63         }
64         for(int i = 0;i < n;i++)
65         {
66             cout<<names[order[i]]<<endl;
67         }
68     }
69     return 0;
70 }