2013年9月4日

UVa 11420 - Chest of Drawers

#include <cstdio>

int main() {
  long long dp[66][66][2] = {};
  dp[1][0][0] = dp[1][1][1] = 1;
  for (int i = 2; i < 66; i++) {
    for (int j = 0; j <= i; j++) {
      dp[i][j][0] = dp[i - 1][j][0];
      if (j) {
        dp[i][j][1] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1];
      }
      if (j != i) {
        dp[i][j][0] += dp[i - 1][j + 1][1];
      }
    }
  }
  int n, s;
  while (scanf("%d%d", &n, &s) && n > 0) {
    printf("%lld\n", dp[n][s][0] + dp[n][s][1]);
  }
  return 0;
}

沒有留言:

張貼留言