poj 2385 Apple Catching 0ms

原题地址

知识点：DP

解题报告

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

using namespace std;

// j部分定义成 31 时不行？ 向前计算的时候有移动 0，..., 30次，共 31 个状态，因此要定义成 32
// d[第i+1分钟][已经移动j次][位于第mov(j)+1棵树] 暴力搜索出结果
int d[1000][32][2];
int T, W;
int apple[1000];

// 因为已知 j 的时候我们已经能够直接算出 k，因此可以直接移除 k 层不必要的循环，使得整个算法更快
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;
}