算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
    有一个长度为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 西月弦 阅读(323) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理