Codeforces #208 Div2. D. Dima and Hares

コード量は少ないけど、Eより苦戦した…。
http://codeforces.com/contest/358/problem/D

問題

３つのN要素の数列A[i]・B[i]・C[i]が与えられる。
0<=i

• 両隣が未処理ならA[i]ポイント
• 隣が片方処理済みならB[i]ポイント
• 両隣が処理済みならC[i]ポイント

ポイント合計の最大値を求めよ。

解法

あるiの処理の結果が(i-1)および(i+1)の処理結果両方に影響するので、iを一方向で処理してO(N)で終えるのは一見難しい。

しかし以下の手順で一方向のDPが可能。
iを大きい順に処理する場合、当然i+1までの結果はDPで確定している。
i番目の最適手は(i-1)とiのどちらを先に処理するかで変わるため、(i-1)を先に処理する場合とiを先に処理する場合の両方を仮定してi番目を決めればよい。

int N,A[3][10000];
int dpdp[2][3001];

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[0][i];
	FOR(i,N) cin>>A[1][i];
	FOR(i,N) cin>>A[2][i];
	
	dpdp[0][N]=A[0][N-1];
	dpdp[1][N]=A[1][N-1];
	for(i=N-1;i>=1;i--) {
		dpdp[0][i]=max(A[0][i-1]+dpdp[1][i+1],A[1][i-1]+dpdp[0][i+1]);
		dpdp[1][i]=max(A[1][i-1]+dpdp[1][i+1],A[2][i-1]+dpdp[0][i+1]);
	}
	
	_P("%d\n",dpdp[0][1]);
}

まとめ

数列のi番目の結果が両隣(i-1)・(i+1)番目の結果に影響する場合、片方の結果を仮定して処理を行えば１次元のDPで処理できる、というテクニックは覚えておこう。