Description：

有 $n$ 个人，第 $i$ 个人在 $l_i$ 离开 $r_i$ 回来，有 $k$ 把钥匙，每个人回来的时候如果他没有钥匙门必须是开的，有钥匙的人可以在离开之后锁门，回来的人也可以选择锁上门或者让门继续开着，问门开着的时间最少是多少。

$1\leqslant k\leqslant n\leqslant 2000$

Solution：

首先发现一个有钥匙的人能控制的范围是从 $l_i$ 开始到下一个发生时间的时刻，只有这部分的开关是由这个人决定的，由于人回来后也可以随便开关，我们可以把结束点也看成是一次决策是否开关的过程，然后如果某个人没有钥匙，那么控制 $r_i$ 的那个区间必须不能关，我们可以发现这形成了一个依赖关系，依赖关系形成了一个树形结构，我们可以在这棵树上树形 $DP$ 一下，也就是设 $f[i][j][0/1]$ 表示子树 $i$ 内分配了 $j$ 个钥匙，根节点有没有钥匙，我们先假设有钥匙一定关门，那么 $0$ 只能朝 $0$ 转移， $1$ 随意，这也就是一个背包，然后可以发现我们可以给一个人钥匙但是不关门，于是我们让 $0$ 统一往 $1$ 转移一下就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 4010

int l[MAXN],r[MAXN];

int s[MAXN];

int val[MAXN];//if you don't choose k,you may get val[k] as cost

int fa[MAXN];//if you don't choose k,you mustn't choose fa[k]

bool tag[MAXN];//whether k is limited

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int siz[MAXN];

int f[MAXN][MAXN][2];

void dp(int k)

{

	memset(f[k],0x3f,sizeof(f[k]));

	siz[k] = 1;

	if(tag[k])f[k][1][1] = 0,f[k][0][0] = val[k];

	else f[k][0][1] = 0,f[k][0][0] = val[k];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dp(e[i].to);

		siz[k] += siz[e[i].to];

		for(int j = siz[k];j >= 0;--j)

		{

			int val1 = 0x3f3f3f3f,val0 = 0x3f3f3f3f;

			for(int l = 0;l <= min(siz[e[i].to],j);++l)

			{

				val1 = min(val1,f[k][j - l][1] + f[e[i].to][l][1]);

				val0 = min(val0,f[k][j - l][0] + min(f[e[i].to][l][0],f[e[i].to][l][1]));

			}

			f[k][j][1] = val1;

			f[k][j][0] = val0;

		}

	}

	for(int l = 1;l <= siz[k];++l)f[k][l][1] = min(f[k][l][1],f[k][l - 1][0]);

	return;

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%d%d",&l[i],&r[i]);

	for(int i = 1;i <= n;++i)s[++s[0]] = l[i],s[++s[0]] = r[i];

	sort(s + 1,s + 1 + s[0]);

	for(int i = 1;i <= n;++i)

	{

		int lef = lower_bound(s + 1,s + 1 + s[0],l[i]) - s;

		int rig = lower_bound(s + 1,s + 1 + s[0],r[i]) - s;

		val[lef] = s[lef + 1] - s[lef];

		fa[lef] = rig - 1;

		tag[lef] = true;

		bool flag = false;

		for(int j = 1;j <= n;++j)if(l[j] < r[i] && r[i] < r[j])flag = true; 

		if(flag)val[rig] = s[rig + 1] - s[rig];

		else val[rig] = 0;

		fa[rig] = rig;

		tag[rig] = false;

	}

	for(int i = 1;i <= 2 * n;++i)

	{

		if(fa[i] != i)add(fa[i],i);

		else add(0,i);

	}

	dp(0);

	int ans = 0x3f3f3f3f;

	for(int i = 0;i <= k;++i)ans = min(ans,min(f[0][i][0],f[0][i][1]));

	cout << ans << endl;

	return 0;

}

Solution2：

另一个做法：

考虑每一条线段，如果两边都是起点，就给左边的考察队加上线段长度，如果都是终点，就给右边的考察队加上线段长度，如果左边终点右边起点，一定会有贡献，如果左边起点右边终点，就在两个点之间连一条权值为线段长度的边，权值代表给这个考察队钥匙可以获得的收益，然后问题就变成了这个图的点数不超过 $k$ 的最大权子图，发现这个图由很多条链构成，因此在链上 $DP$ 就行了。

Code2：

没有代码