题意
有n个人，每个人有一个出现时间a和一个开枪时间b和一个距离d，在任意一个时刻，你可以选择炸人，你要炸一个人的花费是和他的距离d，并且所有的已经出现并且还没开枪的和你距离<=d的人都可以被炸死。问炸死所有人的最小花费是多少。
例如样例就是在第四个时间点炸，这样可以把三个人都炸死。
思路
区间DP。将时间离散化，dp[st][ed]表示炸完在st到ed这段时间的所有人的最小花费是多少。
我们每次都找到只属于当前区间里面的人的花费的最大值。
如果找不到只属于这段区间的点，那么这段区间的花费为0.
否则就从找到的最大花费的这个人的区间左端点开始往右端点扫。代表在这个时间点去炸死这个人。（因为这个人只存活于这个区间，因此要炸死这个人，必须要在这个区间里面炸）。
#include <bits/stdc++.h>
using namespace std;
#define N 605
const int INF = 0x3f3f3f3f;
struct Node {
int l, r, w;
} p[N];
int dp[N][N], x[N];
int main() {
int t; scanf("%d", &t);
while(t--) {
int n; scanf("%d", &n);
int m = 0;
for(int i = 1; i <= n; i++) {
int l, r, w; scanf("%d%d%d", &l, &r, &w);
p[i] = (Node) { l, r, w };
x[++m] = l; x[++m] = r;
}
sort(x + 1, x + 1 + m);
m = unique(x + 1, x + 1 + m) - x - 1;
for(int i = 1; i <= n; i++) {
p[i].l = lower_bound(x + 1, x + 1 + m, p[i].l) - x;
p[i].r = lower_bound(x + 1, x + 1 + m, p[i].r) - x;
}
// memset(dp, INF, sizeof(dp));
for(int len = 1; len <= m; len++) { // dp[st][ed] 消掉st到ed这段区间的人的花费
for(int st = 1; st <= m - len + 1; st++) {
int ed = st + len - 1, id = 0;
for(int i = 1; i <= n; i++) // 找出花费最大的人,这个人只能在属于自己的这段区间解决掉
if(st <= p[i].l && p[i].r <= ed)
if(id == 0 || p[i].w > p[id].w) id = i;
if(id == 0) { dp[st][ed] = 0; continue; }
dp[st][ed] = INF;
for(int gap = p[id].l; gap <= p[id].r; gap++) // 枚举在哪一点去炸掉这个人最优,因为这个人不能被dp[st][gap-1]到dp[gap+1][ed]的点消除
dp[st][ed] = min(dp[st][gap-1] + dp[gap+1][ed] + p[id].w, dp[st][ed]);
}
}
//for(int i = 1; i <= m; i++)
// for(int j = i; j <= m; j++)
// printf("dp[%d][%d] : %d
", i, j, dp[i][j]);
printf("%d
", dp[1][m]);
}
return 0;
}