BZOJ 2958&3269: 序列染色

给出一个长度为 N 由 B、W、X 三种字符组成的字符串 S，你需要把每一个 X 染成 B 或 W 中的一个。
对于给出的 K，问有多少种染色方式使得存在整数 a,b,c,d 使得:
1<=a<=b<c<=d<=N
Sa,Sa+1,...,Sb 均为 B
Sc,Sc+1,...,Sd 均为 W
其中 b=a+K-1,d=c+K-1
由于方法可能很多，因此只需要输出最后的答案对 109+7 取模的结果。

Input

第一行两个正整数 N,K
第二行一个长度为 N 的字符串 S

Output

一行一个整数表示答案%(109+7)。

Sample Input

5 2
XXXXX

Sample Output

4

Solution

首先搞出 B 和 W 的前缀个数，那么可以 $O(1)$ 判某段区间能否为 B 或 W。
然而这样对于超过 K 个的会算重。
对于连续的 B 和 W，考虑用最后 K 个计算，则不会算重（可以在序列最后加一个 X，更好写）。
状态可以设计成 f[i][j][k] 表示考虑前 i 位，状态为 j，这一位选了 k，j 为 0,1,2 分别代表 BW 都没有，只有 B，BW 都有。
转移看代码

###Code

#include<bits/stdc++.h>

#define mod 1000000007

int n,k,bp[1000010],wp[1000010],f[1000010][3][2];
char s[1000010];

int main()
{
    scanf("%d%d%s",&n,&k,s+1);
    s[++n]='X';
    for(int i=1;i<=n;i++)
    {
        bp[i]=bp[i-1]+(s[i]=='B');
        wp[i]=wp[i-1]+(s[i]=='W');
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='B'||s[i]=='X')
            for(int j=0;j<3;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod;
        if(s[i]=='W'||s[i]=='X')
            for(int j=0;j<3;j++)f[i][j][1]=(f[i-1][j][0]+f[i-1][j][1])%mod;
        if(i<=k)continue;
        if((s[i]=='B'||s[i]=='X')&&!(bp[i-1]-bp[i-k-1]))
        {
            f[i][2][0]=(f[i][2][0]+f[i-k][1][1])%mod;
            f[i][1][0]=(f[i][1][0]-f[i-k][1][1])%mod;
        }
        if((s[i]=='W'||s[i]=='X')&&!(wp[i-1]-wp[i-k-1]))
        {
            f[i][1][1]=(f[i][1][1]+f[i-k][0][0])%mod;
            f[i][0][1]=(f[i][0][1]-f[i-k][0][0])%mod;
        }
    }
    int ans=f[n][2][0];
    if(ans<0)ans+=mod;
    printf("%d\n",ans);
}

日期： 2016-12-26

标签： BZOJ DP

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/159/ 查看。