【DP】【CF559E】Gerald and Path

题目

有 n 条线段。 每条线段给定其中一端的位置及长度。 求所有线段覆盖的最大长度。 n≤100。

思路

先按端点排序 设 f i , j , 0..1 f_{i,j,0..1} fi,j,0..1 表示前 i i i 条线段，最靠右的是第 j j j 条，其方向为0或1 考虑如何转移，从小到大枚举 i i i 后面的线段以及它的方向，同时维护枚举过的线段中最靠右的线段以及它的方向。

设线段 j j j 在 p p p 方向的右端点是 o o o；此时枚举到线段 k k k，它的方向为 q q q，长度为 l l l，右端点是 t t t；枚举过的线段中最靠右的线段是 x x x，它的方向为 y y y，右端点是 z z z。

则有转移： f k , x , y = f i , j , p + m i n ( l , t − o ) + z − t f_{k,x,y}=f_{i,j,p}+min(l,t-o)+z-t fk,x,y=fi,j,p+min(l,t−o)+z−t

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=107;
int n,ans,f[N][N][2];
pii a[N];
int main()
{
          
   
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%d%d",&a[i].fi,&a[i].se);
	sort(a+1,a+n+1);
	a[0].fi=-1e9;
	for(int i=0; i<=n; i++) for(int j=0; j<=i; j++) for(int p=0; p<2; p++)
	{
          
   
		ans=max(ans,f[i][j][p]);
		int yjy=a[j].fi+p*a[j].se,mx=-1e9,x,y;
		for(int k=i+1; k<=n; k++) for(int q=0; q<2; q++)
		{
          
   
			int t=a[k].fi+q*a[k].se;
			if(t>mx) mx=t,x=k,y=q;
			f[k][x][y]=max(f[k][x][y],f[i][j][p]+min(a[k].se,t-yjy)+mx-t);
		}
	}
	printf("%d",ans);
}