AGC013D Piling Up

这个题挺妙的

可以设出一个状态:$dp(i,j)$ 表示第 $i$ 次操作完后还有 $j$ 个蓝球的序列个数

转移也非常简单,枚举四种情况即可。

但是这样子的话一个序列可能会从多个初始状态转移而来(方案一样,开始的球个数不一样),这样子就会有重复,该怎么解决?考虑强制一个序列从蓝球个数最小的那个初始状态转移过来,那么这个蓝球最小的初始方案在途中肯定会有变成 $0$ 的时候,所以设 $dp(i,j,k[0,1])$ 在原来的基础上表示 $j$ 是否变成过 $0$,最终答案就是 $\sum\limits_{i=0}^n dp(m,i,1)$。

#include <iostream>
#include <cstdio>

const int MAXN = 3000;
const int MOD = 1e9 + 7;

int n, m, ans;
int dp[MAXN | 1][MAXN | 1][2];

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i <= n; ++i) dp[0][i][i == 0] = 1;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j <= n; ++j) {
      for (int k = 0; k <= 1; ++k) {
        if (k == 0 && j == 0) continue;
        if (j > 0) {
          int kk = k | (j == 1);
          dp[i + 1][j - 1][kk] = (dp[i + 1][j - 1][kk] + dp[i][j][k]) % MOD;
          dp[i + 1][j][kk] = (dp[i + 1][j][kk] + dp[i][j][k]) % MOD;
        }
        if (j < n) {
          dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k]) % MOD;
          dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD;
        }
      }
    }
  }
  for (int i = 0; i <= n; ++i) ans = (ans + dp[m][i][1]) % MOD;
  printf("%d\n", ans);
  return 0;
}
最后修改:2019 年 08 月 16 日 10 : 55 AM

发表评论