Codeforces #676 Div2 E. Swedish Heroes

こードは短い。
http://codeforces.com/contest/1421/problem/E

問題

N要素の整数列Aが与えられる。
隣接する2要素を選択し、それらを取り除いて、代わりにその和を符号反転したものをその位置に挿入することを考える。
最終的に1要素になったとき、得られる値を最大化せよ。

解法

Aの各値は結局+A[i]か-A[i]のいずれかだけ最終的な値に寄与する。
ここで、+-の取り方について、以下の法則がある。

• -を取る要素がM個の場合、(N+M)%3=1である
• +-が交互に来るパターンは不可

なので、M%3の値と、+-が交互に来るパターンが続いてるかどうかを状態としながらDPで先頭から+-を決めていこう。

int N;
ll A[202020];
ll dp[202020][3][2][2];

void solve() {
	int i,j,k,l,r,x,y;
	
	memset(dp,-100,sizeof(dp));
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	if(N==1) {
		cout<<A[0]<<endl;
		return;
	}
	
	
	dp[0][0][0][0]=A[0];
	dp[0][1][1][0]=-A[0];
	int m,p,s;
	for(i=1;i<N;i++) {
		FOR(m,3) FOR(p,2) FOR(s,2) {
			// plus
			dp[i][m][0][s|(p==0)]=max(dp[i][m][0][s|(p==0)],dp[i-1][m][p][s]+A[i]);
			//minus
			dp[i][(m+1)%3][1][s|(p==1)]=max(dp[i][(m+1)%3][1][s|(p==1)],dp[i-1][m][p][s]-A[i]);
		}
	}
	ll ret=max(dp[N-1][((1-N)%3+3)%3][0][1],dp[N-1][((1-N)%3+3)%3][1][1]);
	cout<<ret<<endl;
}

まとめ

この法則にたどり着くのが大変そう。