NOI2009 管道取珠

未分类

考虑 $\sum a_i$ 的实际意义，其实可以看成将原过程做两遍，得到相同结果的方案数。那么直接 DP 即可。

#include <iostream>
#include <cstdio>
const int MAXN = 500;
const int MOD = 1024523;
int n, m;
int dp[2][MAXN | 1][MAXN | 1];
char a[MAXN | 1], b[MAXN | 1];
int main() {
  scanf("%d %d", &n, &m);
  scanf("%s", a + 1);
  scanf("%s", b + 1);
  dp[1][0][1] = 1;
  dp[0][1][0] = 1;
  if (a[1] == b[1]) dp[1][0][0] = dp[0][1][1] = 1;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) {
      for (int k = 0; k <= n; ++k) {
        int l = i + j - k;
        if (l < 0 || l > m || i + j <= 1) continue;
        int o = i & 1, oo = o ^ 1;
        dp[o][j][k] = 0;
        if (i > 0 && k > 0 && a[i] == a[k]) dp[o][j][k] = (dp[o][j][k] + dp[oo][j][k - 1]) % MOD;
        if (i > 0 && l > 0 && a[i] == b[l]) dp[o][j][k] = (dp[o][j][k] + dp[oo][j][k]) % MOD;
        if (j > 0 && k > 0 && b[j] == a[k]) dp[o][j][k] = (dp[o][j][k] + dp[o][j - 1][k - 1]) % MOD;
        if (j > 0 && l > 0 && b[j] == b[l]) dp[o][j][k] = (dp[o][j][k] + dp[o][j - 1][k]) % MOD;
      }
    }
  }
  printf("%d\n", dp[n & 1][m][n]);
  return 0;
}