CF559E Gerald and Path

CF559E

在一个数轴上，有 n n n条线段，你可以决定它为 [ a i , a i + b i ] [a_i,a_i+b_i] [ai​,ai​+bi​]或者是 [ a i − b i , a i ] [a_i-b_i,a_i] [ai​−bi​,ai​]。

问所有线段的并最大是多少。

---

好玩的DP。

按照 a i a_i ai​排序。

设 f i , j f_{i,j} fi,j​表示，考虑了前 i i i个线段，其中延伸到的最右的地方是 j j j，最大的并。

转移的时候如果选择了 [ a i + 1 , a i + 1 + b i + 1 ] [a_{i+1},a_{i+1}+b_{i+1}] [ai+1​,ai+1​+bi+1​]是非常简单的。

问题是如何处理选择 [ a i + 1 − b i + 1 , a i + 1 ] [a_{i+1}-b_{i+1},a_{i+1}] [ai+1​−bi+1​,ai+1​]的情况。

因为可能出现如下图的情况：

这时候我们发现没有办法计算中间空的那一段的贡献。

注意到被第 i + 1 i+1 i+1条线段包含的那个线段是没有用的，于是换种姿势转移：

枚举 k k k，选择线段 [ a k − b k , a k ] [a_k-b_k,a_k] [ak​−bk​,ak​]。 [ i + 1 , k ) [i+1,k) [i+1,k)的线段都钦定向右指。

这样转移得到的右端点是线段 k k k的右端点和 [ i + 1 , k ) [i+1,k) [i+1,k)中线段的右端点的最大值，左端点直接钦定为 k k k的左端点。

可能这样局部的转移并不能得到真正的贡献，但是它不可能比最优答案更有，并且可以感受到全局下肯定存在至少一种方案转移到最优解。

时间复杂度为 O ( n 3 ) O(n^3) O(n3)。

---

代码实现的时候 j j j这一维用了记录线段左右端点的形式来表示。

有点细节（比如初始化）。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 110
#define ll long long
int n;
struct Seg{
	int r[2];
	int l(int t){return t?r[0]:r[0]*2-r[1];}
} s[N];
bool cmps(Seg a,Seg b){return a.r[0]<b.r[0];}
ll f[N][N][2];
int R[N][N],L[N][N];
void upd(ll &x,ll y){x=max(x,y);}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		int a,b;
		scanf("%d%d",&a,&b);
		s[i]={a,a+b};
	}
	sort(s+1,s+n+1,cmps);
	for (int i=1;i<=n;++i){
		R[i][i]=i;
		for (int j=i+1;j<=n;++j)
			R[i][j]=(s[j].r[1]>s[R[i][j-1]].r[1]?j:R[i][j-1]);
	}	
	memset(f,128,sizeof f);
	f[1][1][0]=f[1][1][1]=s[1].r[1]-s[1].r[0];
	for (int k=2;k<=n;++k){
		int id=R[1][k-1],l=s[k].l(0),r=max(s[id].r[1],s[k].r[0]);
		upd(s[id].r[1]>s[k].r[0]?f[k][id][1]:f[k][k][0],r-l);
	}
	for (int i=1;i<n;++i){
		for (int j=1;j<=i;++j)
			for (int t=0;t<2;++t){
				if (f[i][j][t]<0) continue;
				int b=s[j].r[t];
//				printf("f(%d,%d)=%lld\n",i,b,f[i][j][t]);
				ll tmp=f[i][j][t];
				for (int d=0;d<2;++d){
					int l=s[i+1].l(d),r=s[i+1].r[d];
					if (r<=b)
						upd(f[i+1][j][t],tmp);
					else
						upd(f[i+1][i+1][d],tmp+r-max(l,b));
				}
				for (int k=i+2;k<=n;++k){
					int id=R[i+1][k-1],l=s[k].l(0),r=max(s[id].r[1],s[k].r[0]);
					if (r<=b)
						upd(f[k][j][t],tmp);
					else
						upd(s[id].r[1]>s[k].r[0]?f[k][id][1]:f[k][k][0],tmp+r-max(l,b));
				}
			}
	}
	ll ans=0;
	for (int j=1;j<=n;++j)
		for (int t=0;t<2;++t){
			if (f[n][j][t]<0) continue;
			int b=s[j].r[t];
//			printf("f(%d,%d)=%lld\n",n,b,f[n][j][t]);
			ans=max(ans,f[n][j][t]);
		}
	printf("%lld\n",ans);
	return 0;
}