学dp的一定要对数据有一定的敏感性，判断一个题是否是dp直接通过判断是否存在数据的动态转移即可。n <= 20一般是状压， n <= 1000一般就是比较普通的划分区间背包之类dp，也可能要自己搭建dp方程，不过都比较简单。 n <= 1000000可能是斜率或者四边形优化dp，当然也可能是借助二分之类的优化，时间复杂度在O（n）或者O（nlogn）。
这道题就是给你一堆科目，这些科目有名字，提交的截止日期，完成所需要的时间，如果规定时间没完成，每个单位时间分数减一。问你最少减多少。基础的状压dp问题，主要问题在于路径打印，怎么存储路径呢？当前最优状态是由上一个状态加上到达现在状态所需要的元素得到。我们用tail数组存储到达当前最优状态需要添加哪个元素，就可以得到一个路径，最后打印出来即可。代码如下：
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>using namespace std;struct l{string name;int d_tm, f_tm;
}a[105];int dp[1 << 18];
int tail[1 << 18];
int h[25];void out(int x)
{if(x == 0)return;out(x - (1 << tail[x]));cout << a[tail[x]].name << endl;
}int main()
{int T;cin >> T;while(T--) {int n;cin >> n;for(int i = 0; i < n; i++) {cin >> a[i].name >> a[i].d_tm >> a[i].f_tm;}memset(h, 0, sizeof(h));memset(tail, 0, sizeof(tail));for(int i = 0; i <= (1 << n) - 1; i++) {dp[i] = 1000000000;}dp[0] = 0;for(int i = 1; i <= (1 << n) - 1; i++) {int tt = 0;for(int j = 0; j < n; j++) {if((1 << j) & i) {tt += a[j].f_tm;}}for(int j = n; j >= 0; j--) {if((1 << j) & i) {if(dp[i] > dp[i - (1 << j)] + ((tt - a[j].d_tm > 0) ? tt - a[j].d_tm : 0)) {dp[i] = dp[i - (1 << j)] + (tt - a[j].d_tm > 0 ? tt - a[j].d_tm : 0);tail[i] = j;}}}}cout << dp[(1 << n) - 1] << endl;out((1 << n) - 1);}return 0;
}