題目描述：
有一個長度為n(n<1,000,000)的字符串A。有三種字符，'B','W','X'。現(xiàn)在讓你將所有的X要么變成B，要么變成W，構(gòu)造字符串，使得其存在a<=b<c<=d(b-a+1 == d-c+1 == k(k<=n))，其中 Aa...Ab = B Ac...Ad = W。求構(gòu)造方法，mod 1e9+7.
算法分析：
通過對串的某個性質(zhì)來進(jìn)行歸納，從而用動態(tài)規(guī)劃方法解決計數(shù)問題。
類似的題有男人八題第一題，2010福州regional D題。
dp[i,B/W]代表前i個，以B/W結(jié)尾的個數(shù)。
dp[i,B]不必多說了，主要是dp[i,W]
這里可以用來歸納的性質(zhì)是：末尾一共有多少個連續(xù)的W。
當(dāng)末尾W的個數(shù)小于k的時候，答案等于dp[j,B] + ... dp[i-1,B]， 其中j是i左邊的第一個為B的位置。
當(dāng)大于k的時候，除了包含上面的答案以外，對于超出的部分，是含有k個'B'的方案數(shù)總和。
至于如何求含有k個'B'的方案數(shù)總和，這里就不講了，幾乎一模一樣。
#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
西月弦 閱讀(349)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告