自动搬运

查看原文

来自洛谷，原作者为

	PosVII OI(2021.3-2025.3)

搬运于2025-08-24 21:41:31，当前版本为作者最后更新于2021-07-22 11:53:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

此解法使用动态规划。

此方法时间复杂度在最坏情况下是 $O(n^2)$，因此此解法不稳定。

但我的代码是耗时最少的，这说明此解法在数据完全随机时复杂度更低。

入手

如何确定一个字符串是黑白序列呢？我们看一个黑白序列有什么特殊的地方。

一个黑白序列 $str$，我们会发现它的首尾，中间的两个字符分别是 $B$，$W$，$B$，$W$。

那么我们就可以遍历这个字符串，找到其中任何一个特征，我们就可以寻找以其为首、尾或中间两字符的字符串。

那么动态规划的思路自然就出现了，其阶段定义为：

$dp[i]$ 表示变化字符串前 $i$ 个字符中的问号，能使字符串前 $i$ 个字符组成一个黑白序列的方法总数。

阶段定义完毕，我们要确定寻找黑白序列的特征。

很明显，因为黑白序列是对称的，我们只能选择两种特征。

首尾为特征

常规做法。但是我们优化一下。

我们可以知道，前缀和可以快速确定区间中某个东西的数量，我们可以用这个快速判断我们枚举到的字符串是否为黑白序列。

可以拿到 $60pts$。

中间为特征

如何 $O(1)$ 确定是否为黑白序列？我们可以从中间一层一层像寻找回文串一样找。那么我们可以对以同一个字符为中间特征的黑白序列快速寻找。

那么我们只需要枚举中间特征，再一个个扩大范围直到出现不符合的情况时直接跳出枚举循环即可。

请注意，我们在每一次更新左右端点时要看其是否符合条件。下标难以确定的话可以画图思考。

循环时不要枚举字符串的长度，这样会导致你会提前加上没有被更新的值。

Code

#include<bits/stdc++.h>
using namespace std;
const int p=1e9+9;
char str[500006]; 
int dp[500006]={1},n;
int main() {
    cin>>str+1;
    n=strlen(str+1);
    for(int i=1;i<=n;i++) {
    	if(str[i]!='W') {
    		int l=i,r=i+1;
    		for(int j=i;l>=1&&r<=n;j++) {
    			if(str[l]=='W'||str[r]=='B') break;
    			dp[r]=(dp[r]+dp[l-1])%p;
    			l--,r++;
			}
		}
	}
	cout<<dp[n];
    return 0;
}