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; }