P2779 [AHOI2016初中组] 黑白序列 题解
PosVII
·
·
题解
前言
此解法使用动态规划。
此方法时间复杂度在最坏情况下是 O(n^2)，因此此解法不稳定。
但我的代码是耗时最少的，这说明此解法在数据完全随机时复杂度更低。
入手
如何确定一个字符串是黑白序列呢？我们看一个黑白序列有什么特殊的地方。
一个黑白序列 str，我们会发现它的首尾，中间的两个字符分别是 B，W，B，W。
那么我们就可以遍历这个字符串，找到其中任何一个特征，我们就可以寻找以其为首、尾或中间两字符的字符串。
那么动态规划的思路自然就出现了，其阶段定义为：
阶段定义完毕，我们要确定寻找黑白序列的特征。
很明显，因为黑白序列是对称的，我们只能选择两种特征。
**首尾为特征**
------------
常规做法。但是我们优化一下。
我们可以知道，前缀和可以快速确定区间中某个东西的数量，我们可以用这个快速判断我们枚举到的字符串是否为黑白序列。
可以拿到 $60pts$。
**中间为特征**
------------
如何 $O(1)$ 确定是否为黑白序列？我们可以从中间一层一层像寻找回文串一样找。那么我们可以对以同一个字符为中间特征的黑白序列快速寻找。
那么我们只需要枚举中间特征，再一个个扩大范围直到出现不符合的情况时直接跳出枚举循环即可。
请注意，我们在每一次更新左右端点时要看其是否符合条件。下标难以确定的话可以画图思考。
循环时不要枚举字符串的长度，这样会导致你会提前加上没有被更新的值。
**Code**
------------
```cpp
#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;
}
```