P8592 『JROI-8』颅脑损伤 2.0（加强版）

jr_linys · 2023-08-08 21:19:20 · 题解

2023/8/9 把这篇烂题解翻了出来，优化了分析，没那么烂了

2023/8/12 对最新数据进行更新。

题目传送门:普通版加强版

前言

赛时第 3 题推了个柿子调不出来，直接开摆，没看第4题。赛后一看好像还挺简单，小WA一下，开个 long long 就 AC 了。

- - - ## 题目~~大意~~直接 copy 给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$。将每一条线段染成红色或黑色，要求： 1. 任意两条红色线段不相交。 2. 任意一条黑色线段**至少**和一条红色线段相交。请最小化红色线段的长度和，并输出这个长度和。一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交**当且仅当** $l_i\le r_j$ 且 $l_j\le r_i$。 **数据范围** $n\le3000,-10^9\le l_i<r_i\le10^9

困难版 n\le5\times 10^5

O(n^2)

普通版扫一眼数据范围，按出题套路肯定是 O(n^2) DP。

排序一般来说，需要给线段排个序，最基础的两种就是按前端排序和按后端排序。考虑按后端排序，后端相等按前端排序，那么定义 f_i 为按排序后第 i 条线段染成红色,保证前 i 条线段合法，红色线段的总长度。

状态转移设左端点为 x，右端点为 y，上一条红线为第j 条（0\le j<i）（j=0 时第 i 条线段为第 1 条红线，不妨使 x_0=y_0=-\infty）。

因为两条红线不可重叠，所以要保证 y_j<x_i。
又要保证中间剩下的黑线（j<k<i）至少接触一条红线，对于 x_i \le y_k 的黑线可以接触到第 i 条线段，所以只要保证 x_i>y_k 的线段要接触第 j 条线段。

设 p_i 为满足 y_k<x_i 的最后后一条线段。则要保证 \max^{p_i}\limits_{k=j+1} x_k \le y_j。由于 l \in[0,j],x_l\le y_l\le y_j，等价于 \max^{p_i}\limits_{k=0} x_k \le y_j。

那么加上第 i 条线段长度 y_i-x_i，总得（"[ ]"内的表示条件）

f_i= \min^{p_i}\limits_{j=0} [\max^{p_i}\limits_{k=0} x_k \le y_j] f_j+y_i-x_i

统计红色线段要把所有黑色线断覆盖,对于每一个 i，若 \max^{n} \limits_{j=0} x_j \le y_i，则在保证前面合法的情况下，后面的线段也能被这条线段覆盖，所以可以作为最后一条红线。

O(n^2) 代码

可结合注释李姐

提交记录

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=3*1e3,IINF=1e9+10;
const long long INF=1e18;
long long f[N+5],ans=INF;
struct stu{int x,y;}a[N+3];
bool cmp(stu a,stu b){//按后端排序，后端相等按前端排序
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
int main(){
    int n,zmax=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        zmax=max(zmax,a[i].x);//记录最大的左端点
    }
    sort(a+1,a+1+n,cmp);//排序
    a[0].x=-IINF,a[0].y=-IINF;//j=0时第i条线段为第1条红线,不妨使x[0]=y[0]=-无限
    for(int i=1;i<=n;i++){
        int j;
        for(j=i-1;a[j].y>=a[i].x;j--);//跳过y[j]>=x[i]的线段，这些线段能被第i条线段覆盖
        int maxx=-IINF;f[i]=INF;
        for(;j>=0&&a[j].y>=maxx;j--) f[i]=min(f[i],f[j]),maxx=max(maxx,a[j].x);//要满足中间的黑线对第i,j条线，至少触碰一条
        f[i]+=a[i].y-a[i].x;//加上本条线段长度
        if(a[i].y>=zmax) ans=min(ans,f[i]);//判断能否覆盖后面所有的线段，作为最后一条线段 更新
    }
    printf("%lld",ans);
}

O(n\log n)

26号，突然看见有困难版，便想用双指针+线段树优化，然后一直 WA，打了两个小时之后才发现被证伪了......别问为什么，问就是我太睿智了。普通版提交寄录

回归正题。其实上面 O(n^2) 的代码已经有雏形了。

不难看出，第 p_i 条线段一定可以满足转移的条件。而以此线段为右端点向左扩展，y_j 满足不上升，\max^{p_i}\limits_{k=0} x_k \le y_j 满足不下降。

换句话说，可转移的上一条红线是一段区间，而且右端点可以二分，从右端点往左拓展也满足单调性。

所以可以二分左右端点，右端点为 p_i，左端点为满足 \max^{p_i}\limits_{k=0} x_k \le y_j 的第一条。可用数组 maxx[i] 表示 \max^{i} \limits_{k=0} x_k。

然后用线段树区间查询求出 [l,r] 区间最小的 f[j]，然后插入 f[i]。

O(n\log n) 代码