题意：标号为1-n的n种邮票，m个邮票集，每个集里有标号从Li到Ri的邮票，要从中选K个邮票集，使这K个邮票集能覆盖最多种的邮票，问最多能覆盖多少种邮票
思路：区间DP （我：？？？
f[i][j]表示从1 - i 位置选择 j 个集合的覆盖种数
首先它可以从f[i][j] = max(f[i][j], max(f[i-1][j], f[i][j-1]))转移来
其次考虑它能转移到的点
用up[i] 记录覆盖i点的线段最右的点，如果要在 i 后面加一条线段，那么肯定优先取这个（因为它最右，同样加一条线段得到的覆盖长度更长
所以f[i][j]可以转移到f[up[i]][j], if(up[i]) f[up[i]][j] = max(f[i-1][j-1]+up[i]-i+1, f[up[i]][j]);
嘤嘤嘤的哭了
区间DP的话，把区间排个序，然后去掉有完全包含的区间~
#include <map> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 4010; const int maxm = 500100; struct node { int l, r; }a[maxn]; bool cmp(node x, node y) { if(x.l != y.l) return x.l<y.l; return x.r<y.r; } int up[maxn], f[maxn][maxn]; int main() { int T, tt=0; scanf("%d", &T); while(T--) { int n, m, k; scanf("%d%d%d", &n, &m, &k); memset(up, 0, sizeof(up)); memset(f, 0, sizeof(f)); for(int i = 1; i <= m; i++) { scanf("%d%d", &a[i].l, &a[i].r); for(int j = a[i].l; j <= a[i].r; j++) up[j] = max(up[j], a[i].r); } sort(a+1, a+1+m, cmp); for(int i = 1; i <= n; i++) { for(int j = 1; j <= k; j++) { f[i][j] = max(f[i][j], max(f[i-1][j], f[i][j-1])); if(up[i]) f[up[i]][j] = max(f[up[i]][j], f[i-1][j-1]+up[i]-i+1); } } /*for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) printf("f[%d][%d] = %d ", i, j, f[i][j]);*/ printf("Case #%d: %d ", ++tt, f[n][k]); } return 0; }