POJ_2385 Apple Catching

問題
解法
動的計画法をつかう

A(t,p) := (時間tに木pからりんごが落ちてくる) ? 1 : 0
dp[t][p][w] := 時間tで,木pの下にいて,移動回数w以下のときの最大のりんごの数

と定義すると、漸化式は

dp[t][p][w] := max(dp[t][p][w+1], max(dp[t-1][p][w] + A(t,p), dp[t-1][~p][w+1] + A(t,p)))

みたいなかんじになる。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T, W;
int dp[1002][2][32];
int main(){
	scanf("%d %d", &T, &W);
	memset(dp, sizeof(dp), 0);
	for(int t = 1; t <= T; t++){
		int a;
		scanf("%d", &a);
		a--;
		for(int w = W; w >= 0; w--){
			for(int p = 0; p < 2; p++){
				int atp = (a==p) ? 1 : 0;
				dp[t][p][w]
				 = max(dp[t][p][w+1], max(dp[t-1][p][w]+atp, dp[t-1][(p+1)%2][w+1]+atp));
			}
		}
	}
	printf("%d\n", max(dp[T][0][0], dp[T][1][0]));
	return 0;
}