P8591 『JROI-8』颅脑损伤 2.0 题解

· · 题解

第一眼，可以暴搜。

第二眼，可以记忆化。

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

所以考虑 DP。

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

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

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

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

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

r_i<l_x

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

j\in\{k\in(i,x)|r_k<l_x\},r_i\ge l_j

优化一下得：

r_i\ge\max\{l_j\}

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

整合一下得：

f_x=\min\{f_i+r_x-l_x\}

代码就很好写了。

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;
}