【Codeforces 559E】Gerald and Path
动态规划
题目大意：
给定数轴 $n$ 条线段的长度和一个端点的位置，你要确定每条线段另一个端点的位置，使得被这些线段覆盖的总长度最长。求最长的总长度。
题解：
为了避免线段重合的问题，我们对于线段 $[l,r]$，其前缀 $[l,l],[l,l+1],[l,l+2],\cdots,[l,r-1]$ 也可以产生贡献。即若选择这条线段，则 $l\sim r$ 每个位置都要更新贡献，这里的长度为实际算上去的长度而非线段原来的长度。
离散化，对线段按照端点位置排序，令 $f_{i,j}$ 表示前 $i$ 条线段，最右端覆盖到位置 $j$ 时覆盖的最长长度。
考虑这个 $[l,p],[p,r]$ 二选一的两种方法：
向右放（选择 $[p,r]$）。这种情况与之前不会产生冲突，直接转移。$f_{i,j}=\max\{f_{i-1,p}+\mathrm{dist}(p,j)\},j\in[p,r]$。
向左放（选择 $[l,p]$）。这种情况就会产生一个问题：它左边可能存在一条或多条往右的线段，使得右端点在更右边。
我们直接枚举 $k$ 并令 $k\sim i-1$ 这些线段都向右放。令 $R$ 表示右端点最右的位置。则 $f_{i,j}=\max\{f_{k-1,l}+\mathrm{dist}(l,R)\}$。
正确性：如果中间有线段往左放的，那我们这里计算的时候，那个往左放的线段只算进了它的一个前缀的贡献，其冲突部分算在后面这条线段。因此贡献是对的。
直接枚举的复杂度为 $O(n^3)$。考虑 $k$ 从大到小枚举，更新 $R$ 的值。令 $g[R]$ 表示右端点为 $R$ 时的最大答案。
我们直接算出 $g[R]$ 后，还要对其做一遍后缀的处理。就是相当于取前缀计算贡献。具体可以见代码里的处理。
最后每次还要对 $f_i$ 求前缀最大值。
时空复杂度 $O(n^2)$。
Code：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>vec;
const int N=105;
struct lne{
int l,r,p;
inline bool operator<(const lne&rhs)const{return p<rhs.p;}
}d[N];
int n,f[N][N*3],g[N*3];
inline void find(int&x){x=lower_bound(vec.begin(),vec.end(),x)-vec.begin();}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
vec.push_back(-1e9);
for(int i=1;i<=n;++i){
int a,l;
cin>>a>>l;
d[i]=(lne){a-l,a+l,a};
vec.push_back(d[i].l);
vec.push_back(d[i].r);
vec.push_back(d[i].p);
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i=1;i<=n;++i)find(d[i].l),find(d[i].r),find(d[i].p);
const int m=vec.size()-1;
sort(d+1,d+n+1);
for(int i=1;i<=n;++i){
memcpy(f[i],f[i-1],sizeof*f);
int L=d[i].l,R=d[i].r,p=d[i].p;
//left
memset(g,0,sizeof g);
int nr=p;
g[nr]=f[i-1][L]+vec[nr]-vec[L];
for(int j=i-1;j;--j){
nr=max(nr,d[j].r);
g[nr]=max(g[nr],f[j-1][L]+vec[nr]-vec[L]);
}
for(int j=m;j>=L;--j){
f[i][j]=max(f[i][j],g[j]);
g[j-1]=max(g[j-1],g[j]-vec[j]+vec[j-1]);
}
//right
for(int j=p;j<=R;++j)f[i][j]=max(f[i][j],f[i-1][p]+vec[j]-vec[p]);
for(int j=1;j<=m;++j)f[i][j]=max(f[i][j],f[i][j-1]);
}
cout<<f[n][m]<<'\n';
return 0;
}