题目链接 HDU 6249
题意 给定$m$个区间，在这些区间中选出不超过$k$个，求被覆盖的点的数量的最大值。
设$f[i][j]$表示选到第$i$个点并选了$j$个区间的时候能得到的最大答案。
处理到第$i$个点的时候观察所有覆盖$i+1$这个点的线段，找到延伸到最右端的这条线段。
假设该线段延伸到$r$，那么更新$f[r][j + 1]$。
最后枚举答案即可。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 2010; int T;
int ca = 0;
int f[N][N];
int l[N], r[N];
int n, m, k;
int ans; int main(){ scanf("%d", &T);
while (T--){
scanf("%d%d%d", &n, &m, &k);
rep(i, 1, m) scanf("%d%d", l + i, r + i);
rep(i, 0, n + 1) rep(j, 0, m + 1) f[i][j] = 0; f[0][0] = 0;
rep(i, 0, n - 1){
int rr = 0;
rep(j, 1, m){
if (l[j] <= i + 1) rr = max(rr, r[j]);
} rep(j, 0, k) f[i + 1][j] = max(f[i + 1][j], f[i][j]);
if (rr == 0) continue; rep(j, 0, k - 1) f[rr][j + 1] = max(f[rr][j + 1], f[i][j] + rr - i);
} ans = 0;
rep(i, 1, n) rep(j, 0, k) ans = max(ans, f[i][j]);
printf("Case #%d: %d\n", ++ca, ans);
} return 0;
}