【解题报告】BZOJ 1566 [NOI2009]管道取珠

发表于

传送门

$\text{Solution}$

看到这个平方想必都是茫然的。。。

然而有什么方法可以搞掉这个平方呢？数学方法可能比较麻烦。

其实是个套路题

这道题所求的答案就是两个人分别取，取出来的序列相同的方案数

接下来 DP 就稳得一批了

我们用 $dp(k, i, j)$ 表示两个人都取了 $k$ 颗珠子，第一个人在上方水管中取了 $i$ 颗，第二个人在上方水管中取了 $j$ 颗的得到的序列相同的方案总数。

方程就显而易见了：

最终结果显然为 $dp(n+m,n,m)$.

注意滚动数组。

$\text{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Mod 1024523
#define N 505
char a[N], b[N];
int dp[2][N][N];
int main() {
	std::ios::sync_with_stdio(false);
	int n, m, cur = 1;
	std::cin >> n >> m;
	for (int i = n; i >= 1; i--) std::cin >> a[i];
	for (int i = m; i >= 1; i--) std::cin >> b[i];
	dp[0][0][0] = 1;
	for (int k = 1; k <= n + m; k++, cur ^= 1) {
		int lower = std::max(0, k - m), upper = std::min(n, k);
		memset(dp[cur], 0, sizeof dp[cur]);
		for (int i = lower; i <= upper; i++)
			for (int j = lower; j <= upper; j++) {
				int &tmp = dp[cur][i][j];
				if (i && j && a[i] == a[j]) 
					(tmp += dp[cur ^ 1][i - 1][j - 1]) %= Mod;
                if (i && k - j && a[i] == b[k - j])
                	(tmp += dp[cur ^ 1][i - 1][j]) %= Mod;
                if (k - i && j && b[k - i] == a[j])
                	(tmp += dp[cur ^ 1][i][j - 1]) %= Mod;
                if (k - i && k - j && b[k - i] == b[k - j])
                	(tmp += dp[cur ^ 1][i][j]) %= Mod;
			}
	}
	std::cout << dp[cur ^ 1][n][n] << std::endl;
	return 0;
}