POJ2385

DPの練習問題です最初問題を読み間違えて、Wを移動してからW分待つと再び移動できるようになると解釈して、一時間くらい悩みました。英語力の欠如です。

問題の正しい理解ができてからは比較的すぐに実装することができました。ただ、コードは汚いですが。。。

解答時間は1時間半

以下コードです

#include <stdio.h>
#include <algorithm>
using namespace std;

int t, w;
int apple[1000];
int dp[32][1000][2];

int solve(){
  dp[0][0][apple[0]]++;
  for(int i = 1; i < t; i++){
    dp[0][i][0] = dp[0][i-1][0];
    dp[0][i][1] = dp[0][i-1][1];
    dp[0][i][apple[i]]++;
  }
  for(int i = 1; i < w + 1; i++){
    dp[i][0][0] = dp[0][0][0];
    dp[i][0][1] = dp[0][0][1];
    for(int j = 1; j < t; j++){
      dp[i][j][0] = max(dp[i][j-1][0], dp[i-1][j-1][1]);
      dp[i][j][1] = max(dp[i][j-1][1], dp[i-1][j-1][0]);
      dp[i][j][apple[j]]++;
    }
  }
  return max(dp[w][t-1][0], dp[w][t-1][1]);
}

int main(){
  scanf("%d %d", &t, &w);
  for(int i = 0; i < t; i++){
    scanf("%d", &apple[i]);
    apple[i]--;
  }
  printf("%d\n", solve());
  return 0;
}