Codeforces #313 Div1 E. Gerald and Path

シンプルな問題設定。
http://codeforces.com/contest/559/problem/E

問題

1次元の数直線上で、N個のライトがある。
各ライトは座標A[i]に存在し、L[i]の範囲を照らせる。
ライトは左右どちらか片方のみを照らすことができ、左なら区間[A[i]-L[i],A[i]]、右なら区間[A[i],A[i]+L[i]]を照らせる。

各ライトの向きを適切に設定したとき、照らせる区間の総長の最大値を求めよ。

解法

EditorialはO(N^4)解法を紹介しているが、Editorial記事のコメントにO(N^3)解法が書かれているのでそちらを紹介。
Codeforces Round 313 — Extended editoral - Codeforces

まずライトを左から順にソートしておく。
dp[ライト位置][左記のライトかその左側にあるライトのうち、最も右を照らすライト番号][同左照らす向き] := 照らす総長の最大値
という状態を持ち、上記値を更新していく。
なお、向きは0が左、1が右としておく。こうするとA[k]+向き*L[k]でk番のライトが照らすもっとも右の位置を求められる。

すでにdp[i][j][dir]が定まっているとき、この状態からi番の右にあるライトの状態を順次求めていく。
i番～k番のライトのうち最も右まで照らすライト番号をri、またその向きをrdとする。
この場合、k番のライトがkdを向いている状態で最も右まで照らすケースを考えると、
dp[k][ri][rd] = max(dp[k][ri][rd], (A[j]+dir*L[j]) + min(L[k], (A[k]+kd*L[k])-(A[j]+dir*L[j])) - ( (A[ri]+rd*L[ri])-(A[k]+kd*L[k])))
で更新できる。
(A[j]+dir*L[j])はj番までのライトで照らした総長、２項目のmin(L[k], (A[k]+kd*L[k])-(A[j]+dir*L[j]))はk番のライトで照らした総長、( (A[ri]+rd*L[ri])-(A[k]+kd*L[k]))はi～kの間にあるライト(含むk)のうち最も右を照らすライトの距離を示す。
すなわち、j番までのライトで照らした総長にk番のライトで照らした総長を加えるものの、i～k番の間にある他のライトですでに照らされた領域があるならその分減らす、という手順である。

int N;
int A[101],L[101];
pair<int,int> P[101];

int dp[105][105][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	P[N]={-111111111,0};
	N++;
	sort(P,P+N);
	FOR(i,N) A[i]=P[i].first, L[i]=P[i].second;
	
	FOR(x,N+2) FOR(y,N+2) dp[x][y][0]=dp[x][y][1]=-211111111;
	dp[0][0][0]=dp[0][0][1]=0;
	
	int dir,d2;
	int res=0;
	FOR(x,N) {
		FOR(y,x+1) FOR(dir,2) {
			int R=A[y]+dir*L[y];
			int v=dp[x][y][dir];
			
			int mar=-211111112;
			int bk=-1,bd=-1;
			for(k=x+1;k<N;k++) FOR(d2,2) {
				int R2=A[k]+d2*L[k];
				if(mar<R2) mar=R2,bk=k,bd=d2;
				dp[k][bk][bd]=max(dp[k][bk][bd],v+min(L[k],R2-R) - (R2-mar));
				res=max(dp[k][bk][bd],res);
			}
		}
	}
	
	cout<<res<<endl;
}

まとめ

このDPは自力では思いつかないわ…。