POJ(PKU) 2385 Apple Catching

問題文

解法：DP中のDP(?)

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
  
  int t,w,dp[3002][32] = {0};
  
  bool ch[1003];
  
  scanf("%d%d",&t,&w);
  
  for(int i = 0;i < t;i++){
    int tmp;
    scanf("%d",&tmp);
    if(tmp == 1){
      ch[i+1] = true;
    }else{
      ch[i+1] = false;
    }
  }
  
  for(int i = 1;i <= t;i++){
    dp[i][0] = dp[i-1][0];
    if(ch[i] == true)dp[i][0]++;
  }
  
  for(int i = 1;i <= t;i++){
    for(int j = 1;j <= w;j++){
      int pou=0;
      bool flag = false;
      if(j % 2 == 0)flag = true;
      if(flag == ch[i])pou++;
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+pou;
    }
  }
  
  int ans = 0;
  
  for(int i = 0;i <= w;i++){
    ans = max(ans,dp[t][i]);
  }
  
  printf("%d\n",ans);
  
  return 0;
  
}