区间题套路：考虑所有区间互不相交的情况，并考虑互相包含的区间之间的关系。
此题类似。
首先考虑所有区间互不相交的情况。
区间按左端点排序（此时右端点一定也有序），这样一组必定是一段区间。
并且只要交集不为空，交集大小即这一组第一个区间右端点减去最后一个区间左端点。
于是得到一个 DP：设 \(f_{i,j}\) 表示前 \(i\) 个区间分 \(j\) 组的最大答案。
转移即枚举该组的区间，得 \[f_{i,j} = \max\limits_{1\le k\le i,t_k > s_i}(f_{k-1,j} + t_k - s_i)\]
然后考虑互相包含的区间之间的关系。
若区间 \(a,b\) 满足 \(b \subseteq a\)，则只有以下两种情况：
1. \(a,b\) 与某些区间在同一组。 2. \(a\) 单独在一组，\(b\) 与某些区间在一组。 证明：若 \(a\) 与某些区间在一组，则将 \(a\) 移动到 \(b\) 所在的组，\(a\) 原来的组交集不会变小，\(b\) 所在的组答案不变。
于是把不包含别的区间的区间拉出来 DP，枚举这一部分在 \(p\) 组中占了多少组，别的组贪心地在另一部分取更大的区间，剩下的分进任意一个所包含的区间所在的组（答案不变）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const int N = 200;
int n,p;
int vis[N + 5];
int tot1,tot2;
int f[N + 5][N + 5],ans = -0x3f3f3f3f;
struct note
{
int l,r;
inline bool operator<(const note &o) const
{
return l < o.l;
}
inline bool operator>(const note &o) const
{
return r - l > o.r - o.l;
}
} w[N + 5],a[N + 5],b[N + 5];
int main()
{
freopen("factory.in","r",stdin),freopen("factory.out","w",stdout);
scanf("%d%d",&n,&p);
for(register int i = 1;i <= n;++i)
scanf("%d%d",&w[i].l,&w[i].r);
for(register int i = 1,flag;i <= n;++i)
{
flag = 1;
for(register int j = 1;j <= n;++j)
if((i ^ j) && !vis[j] && w[i].l <= w[j].l && w[j].r <= w[i].r)
{
flag = 0;
break;
}
flag ? (a[++tot1] = w[i]) : (vis[i] = 1,b[++tot2] = w[i]);
}
sort(a + 1,a + tot1 + 1),sort(b + 1,b + tot2 + 1,greater<note>()),memset(f,-0x3f,sizeof f),f[0][0] = 0;
for(register int i = 1;i <= tot1;++i)
for(register int j = 1;j <= p;++j)
for(register int k = 1;k <= i;++k)
if(a[k].r > a[i].l)
f[i][j] = max(f[i][j],f[k - 1][j - 1] + a[k].r - a[i].l);
for(register int i = p,sum = 0;i && p - i <= tot2;sum += b[p - i + 1].r - b[p - i + 1].l,--i)
i <= tot1 && (ans = max(ans,f[tot1][i] + sum));
printf("%d\n",ans);
}