[cf559E]Gerald and Path

将所有线段的端点（即$a_{i}$和$a_{i}pm l_{i}$）离散，并按照$a_{i}$从小到大排序

定义$f_{i,,j}$表示前$i$条线段在位置$j$之前最多能覆盖的长度（默认覆盖到$j$，允许覆盖到$j$之后，但该部分不计入覆盖的长度），转移对第$i$条线段的方向分类讨论：

（关于"默认覆盖到$j$"，完整的描述即默认$[a_{i},j]$已经被覆盖，即之后覆盖不计算贡献）

1.若第$i$条线段向右覆盖，即有
$$
f_{i,j}=egin{cases}f_{i-1,j}&(jle a_{i}或a_{i}+l_{i}<j)\f_{i-1,a_{i}}+(j-a_{i})&(a_{i}<jle a_{i}+l_{i})end{cases}
$$
2.若第$i$​条线段向左覆盖，即有
$$
f_{i,j}=egin{cases}f_{i-1,j}&(jle a_{i}-l_{i})\f_{i-1,a_{i}-l_{i}}+(j-(a_{i}-l_{i}))&(a_{i}-l_{i}<jle a_{i})\max_{1le kle i}left(f_{k-1,a_{i}-l_{i}}+min(a_{k}+l_{k},j)-(a_{i}-l_{i}) ight) &(a_{i}<j)end{cases}
$$
这里解释一下第3种情况，考虑枚举最终右端点的位置（如果选$k=i$即不存在，注意此时中间应为$a_{k}$），那么注意到在其之后的直线如果向前覆盖到$a_{i}-l_{i}$之前，即已将整个$[a_{i}-l_{i},a_{i}]$全部覆盖，那么显然一定不如向右覆盖，因此即只需要考虑其之前的线段即可

综上，时间复杂度为$o(n^{3})$，可以通过

事实上，还可以进行优化，复杂度的瓶颈在于向左覆盖时$a_{i}<j$的部分，显然该部分可以用线段树优化（只需要对$a_{k}+l_{k}$和$j$的大小关系分类讨论即可），时间复杂度即降为$o(n^{2}log n)$

#include<bits/stdc++.h>
using namespace std;
#define N 105
map<int,int>mat;
map<int,int>::iterator it;
int n,m,a[N],l[N],pos[N*3],id[N],posl[N],posm[N],posr[N],f[N][N*3];
bool cmp(int x,int y){
    return a[x]<a[y];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&l[i]);
        mat[a[i]]=mat[a[i]-l[i]]=mat[a[i]+l[i]]=1;
    }
    for(it=mat.begin();it!=mat.end();it++){
        mat[(*it).first]=++m;
        pos[m]=(*it).first;
    }
    for(int i=1;i<=n;i++)id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++){
        int x=id[i];
        posl[i]=mat[a[x]-l[x]];
        posm[i]=mat[a[x]];
        posr[i]=mat[a[x]+l[x]];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int x=id[i];
            f[i][j]=f[i-1][j];
            if (a[x]<pos[j])f[i][j]=max(f[i][j],f[i-1][posm[i]]+min(pos[j]-a[x],l[x]));
            if ((a[x]-l[x]<pos[j])&&(pos[j]<=a[x]))f[i][j]=max(f[i][j],f[i-1][posl[i]]+(pos[j]-(a[x]-l[x])));
            if (a[x]<pos[j]){
                f[i][j]=max(f[i][j],f[i-1][posl[i]]+l[x]);
                for(int k=1;k<i;k++)f[i][j]=max(f[i][j],f[k-1][posl[i]]+min(a[id[k]]+l[id[k]],pos[j])-(a[x]-l[x]));
            }
        }
    printf("%d
",f[n][m]);
    return 0;
}