POJ 2385 Apple Catching 0ms Solution

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

// Why defining j part as 31 doesn't work? When calculating forward, there are movements of 0, ..., 30 times, totaling 31 states, so it needs to be defined as 32
// d[i+1-th minute][already moved j times][located at tree mov(j)+1] Brute force search for result
int d[1000][32][2];
int T, W;
int apple[1000];

// Since we can directly calculate k when j is known, we can directly remove the unnecessary k-level loop to make the entire algorithm faster
int mov(int a) {
  if ((a & 0x1) == 0) return 0;
  return 1;
}

int main() {
  scanf("%d %d", &T, &W);
  int i, j, k;
  for(i=0;i<T;++i) {
    scanf("%d", &apple[i]);
    apple[i]--;
  }
  if (apple[0] == 0) {
    d[0][0][0] = 1;
    d[0][1][1] = 0;
  } else {
    d[0][0][0] = 0;
    d[0][1][1] = 1;
  }

  for(i=0;i<T-1;++i) {
    for(j=0;j<=W;++j) {
      if (mov(j) == apple[i+1]) {
        d[i+1][j][mov(j)] = max(d[i+1][j][mov(j)], d[i][j][mov(j)] + 1);
        d[i+1][j+1][mov(j+1)] = max(d[i+1][j+1][mov(j+1)], d[i][j][mov(j)]);
      } else {
        d[i+1][j+1][mov(j+1)] = max(d[i+1][j+1][mov(j+1)], d[i][j][mov(j)] + 1);
        d[i+1][j][mov(j)] = max(d[i+1][j][mov(j)], d[i][j][mov(j)]);
      }
    }
  }
  cout << *max_element(d[T-1][0], d[T-1][0] + 2*(W+1)) << endl;
  return 0;
}