【学习笔记】CF559E Gerald and Path

本文主要是介绍【学习笔记】CF559E Gerald and Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先，设每个线段为 $(p, l, r)$ ，即覆盖 $[l, p]$ 或 $[p, r]$ 之一。将线段 按 $p$ 从小到大排序（因为只知道 $p$ 的大小关系），以及将端点离散化。

题目数据范围很小，可以考虑设计两个维度。设 $f_{i,j}$ 表示只考虑前 $i$ 个线段，以及只考虑数轴上离散化后前缀 $j$ 时能覆盖的最大长度

考虑每次加入一个线段 $(p, l, r)$ 的变化（省略下标 $i$ ），转移如下：

$1.1$ （向右）： $\forall k\in [p+1,r],f_{i,k}=\max(f_{i,k},f_{i-1,p}+\text{dist(p,k)})$ ，其中 $\text{dist(i,j)}$ 表示离散化后 $i, j$ 原始坐标之差

$1.2$ （向左）： $\forall k\in [l,cnt]$ ，设 $j$ 表示最大的满足 $\max(p,\max_{j<x<i}r_j)\ge k$ 的位置， $f_{i,k}=\max(f_{i,k},f_{j,l}+\text{dist(l,k)})$

$1.3$ 做前缀 $\max$

其中第二种转移可以用双指针维护。

复杂度直接做到了 $O(n^2)$ 。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=305;
int n,cnt,lsh[N],f[N][N];
struct node{int p,l,r;bool operator <(const node &a)const{return p<a.p;}
}q[N];
int get(int x){return lower_bound(lsh+1,lsh+1+cnt,x)-lsh;
}
void add(int &x,int y){x=max(x,y);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){int a,l;cin>>a>>l;q[i]={a,a-l,a+l},lsh[++cnt]=a,lsh[++cnt]=a-l,lsh[++cnt]=a+l;}sort(lsh+1,lsh+1+cnt),cnt=unique(lsh+1,lsh+1+cnt)-lsh-1;for(int i=1;i<=n;i++){q[i].p=get(q[i].p),q[i].l=get(q[i].l),q[i].r=get(q[i].r);}sort(q+1,q+1+n);for(int i=1;i<=n;i++){int p=q[i].p,l=q[i].l,r=q[i].r;for(int k=p+1;k<=r;k++)add(f[i][k],f[i-1][p]+lsh[k]-lsh[p]);int j=i-1,mx=p;for(int k=l;k<=cnt;k++){while(j&&mx<k)mx=max(mx,q[j].r),j--;if(mx>=k)add(f[i][k],f[j][l]+lsh[k]-lsh[l]);}for(int j=1;j<=cnt;j++)add(f[i][j],f[i][j-1]),add(f[i][j],f[i-1][j]);}cout<<f[n][cnt];
}