这题比较有意思，暴力搜索必然tle，可以用状态压缩dp解决。

我们先不考虑完成所有作业的扣分，而考虑其一个子集的情况。

假设我们得到了完成某子集S对应的作业最少扣分，我们试着向该子集中增加一个元素a，那么我们将得到一个新的集合S1。

从而f(S1) = min(g(S^')),  S^'⊂S, 且#(S^') = #(S) - 1。

 其中g函数仅依赖于集合S^'与元素e = (S - S')。

如果我们能够在处理S之前将其所有真子集都处理完毕，那么S可以直接由原状态导出。

于是当更新到S为全集的时候，答案也就得到了。

考虑用二进制表示状态，二进制数某一位为1或0代表同位次的元素属于（不属于）该集合。

所有子集的数值大小都比原集合小。

将二进制数从小到大扫描一遍即可。

这就是所谓的状态压缩dp。

复杂度O(n * 2^n)。

 

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6 typedef __int64 LL; 7  8 const int inf = 0x3f3f3f3f; 9 const int maxn = 100 + 10;10 const int maxm = 1 << 16;11 12 char s[20][maxn];13 int n, high;14 struct Node{15     int t, dl;16 }node[maxn];17 int dp[maxm];18 int tc[maxm], pre[maxm], ans[20];19 20 void print(){21     printf("%d\n", dp[high]);22     int p = high, k = 0;23     while(p){24         ans[k++] = pre[p];25         p -= 1 << pre[p];26     }27     for(int i = k - 1; i >= 0; i--) puts(s[ans[i]]);28 }29 30 int main(){31     int T;32     scanf("%d", &T);33     while(T--){34         scanf("%d", &n);35         for(int i = 0; i < n; i++){36             scanf("%s%d%d", s[i], &node[i].dl, &node[i].t);37         }38         high = (1 << n) - 1;39         memset(dp, inf, sizeof dp);40         dp[0] = 0;41         for(int i = 1; i <= high; i++){42             for(int j = n - 1; j >= 0; j--){43                 int tem = 1 << j;44                 //update the current state by enumerating the new element45                 if(tem & i){46                     //i is the current state while (i - tem) is the previous state47                     int p = max(0, node[j].t + tc[i - tem] - node[j].dl);48                     if(p + dp[i - tem] < dp[i]){49                         dp[i] = p + dp[i - tem];50                         tc[i] = node[j].t + tc[i - tem];51                         pre[i] = j;52                     }53                 }54             }55         }56         print();57     }58     return 0;59 }