自动搬运

查看原文

来自洛谷，原作者为

	xwh_Marvelous 谁也打不过我学什么 OI

搬运于2025-08-24 22:40:29，当前版本为作者最后更新于2022-10-25 20:42:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一眼，可以暴搜。

第二眼，可以记忆化。

第三眼，可以记忆化改 DP。

所以考虑 DP。

实际上对于普及组而言，大多数 DP 题都可以记忆化搜索解决，这里只介绍 DP 解法。

首先要将线段按 $l$ 排序，这样能确保 DP 的顺序不会出问题。

我们设计状态 $f_x$ 表示将第 $x$ 条线段染成红色且 $1$ 到 $x$ 都是合法方案的最小代价。

接下来考虑 $f_x$ 如何转移，假设转移枚举到 $f_i$。

首先根据要求一，任意两条红色线段不相交，得到：

然后根据要求二，任意一条黑色线段至少和一条红色线段相交，得到：

优化一下得：

这实际上是确保 $i$ 到 $x$ 中间的不与线段 $x$ 相交的线段染成黑色后还能与染成红色的线段 $i$ 相交。

整合一下得：

代码就很好写了。

AC code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct line{ll l,r;bool operator<(const line &x)const{return this->l!=x.l?this->l<x.l:this->r<x.r;}}a[3005];
ll f[3005],ans=LONG_LONG_MAX;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].l,&a[i].r);
	sort(a+1,a+1+n);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	a[0].r=-2e9;
	for(int i=1;i<=n;i++){
		ll tot=-2e9;
		for(int j=i-1;j>=0;j--){
			if(a[j].r>=a[i].l||a[j].r<tot)continue;
			f[i]=min(f[i],f[j]+a[i].r-a[i].l);
			tot=max(tot,a[j].l);
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i].r>=a[n].l)ans=min(ans,f[i]);
	}
	printf("%lld",ans);
	return 0;
}