Codeforces #376 Div2 E. Funny Game

上位陣の回答は簡潔だね。
http://codeforces.com/contest/731/problem/E

問題

N要素の数列A[i]を用いて、２人で交互にターンが回ってくるゲームを行う。

自分のターンでは、数列の先頭を２要素以上何要素か選択する。
するとその総和の分自分の得点が加算される。また、その際選んだ要素が全て数列から消え、代わりに先頭に総和が挿入される。
数列が１要素になったら終了する。

２人が互いのスコア差を最大にしようと最適に振る舞ったとき、先手は後手に対し何点差をつけられるか。

解法

S[i]=sum(A[0..i])とする。
以下の状態を考える。
dp[i] := 先頭i要素が削除され、代わりのその総和S[i]が先頭にあるとする状態で、そこからゲーム終了まで最大で何点差をつけられるか。
この状態で元の数列でx要素目(x＞i)相当までを選択すると、プレイヤーにはS[x]だけスコアが入る。
相手はその後dp[x]だけスコアが入る。

よって、dp[i] = max(S[x]-dp[x])をiが大きい順に求めていけば良い。(1-originで)dp[1]が解。
maxはRMQ等使っても良いが、dp[i]は大きい順に決まっていくのでその都度max(S[x]-dp[x])を求めていけば良い。

int N;
int A[202020];
ll S[202020];
ll dp[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	ll ma=-1LL<<60;
	for(i=N-1;i>=1;i--) {
		ma=max(ma,S[i+1]-dp[i+1]);
		dp[i]=ma;
	}
	cout<<dp[1]<<endl;
	
	
	
}

まとめ

Funny…？