【链接】
acm.hdu.edu.cn/showproblem.php?pid=6249
【题意】
给你m个区间，要求你选出k个区间，使得区间并的覆盖范围最大
1≤T≤100
1≤K≤M
1≤N,M≤2000
1≤Li≤Ri≤N
【思路】
一开始我们得出错误的dp转移：
先按右端点排序，dp[i][j]表示前i个区间集合，当前已经选了j个的最大的覆盖范围，但是显然需要再枚举是哪个右端点转移过来的。显然是O(n^3)的复杂度显然不行，但是我们错误地记录了转移到的最大的贡献来自于哪个右端点，其实这样是错误的。哎，思维不够严谨。
正确的做法是：改变dp状态设计。可以观察到，n的范围只有2000，那么这个条件肯定是要用的。我们设计dp[i][j]表示当前位于值为i的点，并且选了j个区间的最大dp值，显然，对于一个点，我们会选择能覆盖这个点的最远的区间右端点，维护一下这个，对于每个点，选与不选转移即可
【代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
int L[maxn], R[maxn];
int dp[maxn][maxn];
int up[maxn];int main() {int t;scanf("%d", &t);int ca = 0;while (t--) {memset(dp, 0, sizeof(dp));memset(up, 0, sizeof(up));int n, m, k;scanf("%d%d%d", &n, &m, &k);for (int i = 0; i < m; i++) {int x, y;scanf("%d%d", &x, &y);for (int j = x; j <= y; j++) {up[j] = max(up[j], y);}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= k; j++) {dp[i][j] = max(dp[i][j], dp[i - 1][j]);if (up[i]) {dp[up[i]][j] = max(dp[up[i]][j], dp[i - 1][j-1] + up[i] - i + 1);}}}printf("Case #%d: %d\n", ++ca, dp[n][k]);}
}