PKU 2385 Apple Catching

http://poj.org/problem?id=2385
りんごの木、1と2があって、t分間に1分間隔でどちらかの木からりんごが落ちてくる。
どちらかのりんごの木の下にいるとき、その木から落ちてくるりんごは必ず取れるものとする。
このとき、木1と木2の間を移動する回数がw回以下の制限されているもとで、取れるりんごの個数の最大値を求めるという問題。

動的計画法、dp[i][j][k]=i分までにj回以内の移動回数で、kのりんごの樹の下にいるときに取れる最大のりんごの数、というような感じで解きました。

int dp[1001][32][2];
int in[1000];

main(){
  int t,w;
  cin>>t>>w;
  rep(i,t){
    cin>>in[i];
    --in[i];
  }

  int ans=0;
  
  rep(i,t){
    rep(j,w+1){
      int tans=0;
      dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+(in[i]==0));
      dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][1]+(in[i]==1));

      dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j][1]+(in[i]==0));
      dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j][0]+(in[i]==1));
      dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j+1][0]+(in[i]==0));
      dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j+1][1]+(in[i]==1));
      tans=max(tans,dp[i+1][j][0]);
      tans=max(tans,dp[i+1][j][1]);
      ans=max(ans,tans);
    }
  }
  cout<<ans<<endl;
}