PKU 2385 Apple Catching

問題文→2385 -- Apple Catching

りんごが1分ごとに2本の木のいずれかから落ちてくる。2本の木を決められた回数内行き来して落ちてくるりんごをキャッチする。　キャッチできるりんごの合計の最大値を求めよ。

とりあえずメモ化再帰を書いてみる。しかしこれではなぜかWAした。

int dfs(int n,int w,int a){
  int res;
  if(n==T) return 0;
  if(dp[n][w][a]>0) return dp[n][w][a];
  else if(w<0) return dp[n][w][a]=dfs(n+1,w,a);
  else return dp[n][w][a]=max(dfs(n+1,w,a)+apple[n+1][a],dfs(n+1,w-1,(a==1?2:1))+apple[n+1][(a==1?2:1)]);
}

dpになおしてみる。 dp[n][w][a]=n分目までにw回移動してaの木にいるときにキャッチしたりんごの数とする。しかしこれでもWAしたのでここ→PKU 2385 Apple Catching - 敗戦記を参考にさせていただいたら通った。

同じ事してるはずなのに... なぜだろうorz

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<cstdlib>
#include<climits>
#include<cstring>
#include<queue>
#include<deque>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define INF 99999999
#define EPS 0.0001
using namespace std;
int T,W;
int apple[2000];
int dp[2000][50][10];
int main(){
  memset(apple,0,sizeof(apple));
  memset(dp,0,sizeof(dp));
  cin>>T>>W;
  REP(i,T){
    int t; cin>>t;
    apple[i]=t-1;
  }
  int res=0;
  for(int i=0;i<T;i++){
    for(int j=0;j<=W;j++){
      dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+(apple[i]==0));
      dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][1]+(apple[i]==1));
      dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j][1]+(apple[i]==0));
      dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j][0]+(apple[i]==1));
      dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j+1][0]+(apple[i]==0));
      dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j+1][1]+(apple[i]==1));
      int tmp=0;
      tmp=max(tmp,dp[i+1][j][0]);
      tmp=max(tmp,dp[i+1][j][1]);
      res=max(res,tmp);
    }
  }
  cout<<res<<endl;
}