题目描述：
有一个长度为n(n<1,000,000)的字符串A。有三种字符，'B','W','X'。现在让你将所有的X要么变成B，要么变成W，构造字符串，使得其存在a<=b<c<=d(b-a+1 == d-c+1 == k(k<=n))，其中 Aa...Ab = B Ac...Ad = W。求构造方法，mod 1e9+7.
算法分析：
通过对串的某个性质来进行归纳，从而用动态规划方法解决计数问题。
类似的题有男人八题第一题，2010福州regional D题。
dp[i,B/W]代表前i个，以B/W结尾的个数。
dp[i,B]不必多说了，主要是dp[i,W]
这里可以用来归纳的性质是：末尾一共有多少个连续的W。
当末尾W的个数小于k的时候，答案等于dp[j,B] + ... dp[i-1,B]， 其中j是i左边的第一个为B的位置。
当大于k的时候，除了包含上面的答案以外，对于超出的部分，是含有k个'B'的方案数总和。
至于如何求含有k个'B'的方案数总和，这里就不讲了，几乎一模一样。
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = int(1e6)+10;
const int mod = int(1e9)+7;
char ch[N];
ll nearb[N],neara[N],sumb[N][2],haveb[N][2],all[N],dp[N][2],sum[N][2];
int main(){
int n,k;
#define havab haveb
while(~scanf("%d%d",&n,&k)){
scanf("%s",ch);
all[0]=1;
for(int i=1;i<=n;i++){
char x = ch[i-1];
if(x == 'B') nearb[i] = i, neara[i] = neara[i-1];
else if(x == 'W') nearb[i] = nearb[i-1], neara[i] = i;
else nearb[i] = nearb[i-1] , neara[i] = neara[i-1];
if(x == 'X') all[i] = (all[i-1] <<1) % mod;
else all[i] = all[i-1];
int j= neara[i],p = i - k;
if(p < j) p = j-1;
if(p<0) p=0;
if(x == 'W') {
haveb[i][1] = 0;
haveb[i][0] = (havab[i-1][0] + havab[i-1][1]) % mod;
}
else {
if(x == 'B') havab[i][0] = 0;
else havab[i][0] = (havab[i-1][0] + havab[i-1][1]) % mod;
havab[i][1] = (sumb[i-1][0] - sumb[p][0] + mod) % mod;
if(i-j>=k) {
havab[i][1] += all[p];
havab[i][1] %= mod;
}
}
// cout<<"i: "<<i<<" "<<haveb[i][0]<<" "<<haveb[i][1]<<endl;
sumb[i][0] = (sumb[i-1][0] + haveb[i][0] ) % mod;
sumb[i][1] = (sumb[i-1][1] + haveb[i][1] ) % mod;
j = nearb[i];
p = i - k;
if(p < j) p = j-1;
if(p<0) p=0;
if(x == 'B') {
dp[i][0] = 0;
dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % mod;
}
else {
if(x == 'W') dp[i][1] = 0;
else dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % mod;
dp[i][0] = (sum[i-1][1] - sum[p][1] + mod) % mod;
if(i-j>=k) {
dp[i][0] += sumb[p][1] - sumb[j-1][1] + mod;
dp[i][0] %= mod;
}
}
// cout<<j<<" "<<p<<endl;
// cout<<"dp: "<<dp[i][0]<<" "<<dp[i][1]<<endl;
sum[i][0] = (sum[i-1][0] + dp[i][0]) % mod;
sum[i][1] = (sum[i-1][1] + dp[i][1]) % mod;
}
cout<<(dp[n][0] + dp[n][1]) % mod <<endl;
}
}
posted on 2012-07-21 19:13
西月弦 阅读(330)
评论(0) 编辑 收藏 引用 所属分类:
解题报告