考虑把总区间长度减去最多能减少的区间长度
把所有区间离散化，对每一小段计算贡献
分类讨论一波，对于边界 $i,i+1$ ，设它们之间距离 $d$，$i$ 属于 $x$ 考察队的边界，$i+1$ 属于 $y$ 考察队的边界：
$i$ 为左边界，$i+1$ 为左边界，显然如果给 $x$ 钥匙就可以让这一段时间关门，给 $x$ 的贡献 $val[x]$ 加上 $d$ ，表示给 $x$ 钥匙得到的贡献
$i$ 为左边界，$i+1$ 为右边界，如果 $x=y$ ，显然给 $x$ 钥匙就可以让这段时间关门，那么给 $val[x]$ 加 $d$
如果不为同一个考察队，那么如果要得到这一段的价值就必须同时给两个考察队钥匙，就从 $x$ 往 $y$ 连一条边权为 $d$ 的单向边，表示 $x,y$ 都有钥匙得到的贡献
$i$ 为右边界，$i+1$ 为左边界，那么这一段显然关门就好，直接给答案加上 $d$
$i$ 为右边界，$i+1$ 为右边界，那么给 $y$ 钥匙就可以让这段时间关门，所以 $val[y]+=d$
（注意此时不用考虑 $x$ 能不能进来，$x$ 在之前就已经考虑过了）
发现这的图是由几条链组成的，所以可以对每条链分别 $dp$
设 $f[i][j][1/0]$ 表示前 $i$ 个点，给了 $j$ 个点钥匙，当前点 $i$ 选$/$不选的最大代价
具体实现起来还有点难度，看代码吧
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=5e3+,INF=1e9+;
int n,K,tot,ans;
int pos[N],val[N],eval[N],nex[N];//eval是边的价值，nex存边
map <int,int> mp;//维护某个位置的编号
int id[N],f[][][];//id是新的编号(同一条链的编号连续),f是dp数组
bool vis[N];//是否被重新编号过
void dfs(int x) { vis[ id[++tot]=x ]=; if(nex[x]) dfs(nex[x]); }//给一条链的每个节点编号
int main()
{
n=read(),K=read();
int l,r;
for(int i=;i<=n;i++)
{
l=read(),r=read();
mp[l]=i<<; mp[r]=i<<|;//编号
pos[i]=l; pos[n+i]=r;//存位置，注意位置都是左闭右开的！
}
sort(pos+,pos+(n<<)+);//排序
int res=;
for(int i=;i<(n<<);i++)//对每一小段分类讨论
{
l=pos[i],r=pos[i+];
int ld=mp[l],rd=mp[r];
if( !(ld&) )//i为左边界
{
if( !(rd&) ) val[ld>>]+=r-l;//i+1为左边界
else//i+1为右边界
{
if( (ld|)==rd ) val[ld>>]+=r-l;//如果属于同一点
else nex[ld>>]=(rd>>),eval[ld>>]=r-l;
}
}
else//i为右边界
{
if( !(rd&) ) res+=r-l;//i+1为左边界
else val[rd>>]+=r-l;//i+1为右边界
}
}
for(int i=n<<;i;i--)//注意从后往前找，要让链的节点编号连续
{
int d=mp[pos[i]];
if( !(d&) && !vis[d>>] ) dfs(d>>);
}
memset(f,~0x3f,sizeof(f));//记得初始化
f[tot+][][]=;
for(int i=tot;i;i--)
{
f[i][][]=;
for(int j=;j<=min(K,tot-i+);j++)
{
f[i][j][]=max(f[i+][j][],f[i+][j][]);
f[i][j][]=max(f[i+][j-][], f[i+][j-][]+eval[ id[i] ] )+val[ id[i] ];
}
}
printf("%d", pos[n<<]-pos[]-res-max(f[][K][],f[][K][]) );
return ;
}