当前位置:网站首页>Bzoj2958 & 3269: sequence staining (DP)

Bzoj2958 & 3269: sequence staining (DP)

2020-12-07 15:04:43 osc_ 1q5l9zt9

Subject portal
Metaphysics can't really .

solution :
f[i][j][k] It means the first one i position ,k=0 fill B,k=1 fill W.
j=0 The length of a paragraph is K Successive B None .
j=1 There is a paragraph with the length of K Successive B.
j=2 There is a paragraph with the length of K Successive W.
Because you have to have B It's continuous W continuity .
that j=2 Definitely from j=1 Transfer





Keep it continuous B There must be one behind W, Successive W There's a B, The answer is f[n+1][2][0]
Suppose this one chooses B Obviously there is
f[i][j][0]=f[i-1][j][1]+f[i-1][j][0]
if(i-k+1 To i No, W)f[i][1][0]=f[i][1][0]+f[i-k][0][1];
But there will be repetition , because f[i][0][0] It's a random shift , There may already be B 了 , therefore :
if(i-k+1 To i No, W)f[i][0][0]=f[i][0][0]-f[i-k][0][1];




Code implementation :

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int b[1110000],w[1110000],f[1110000][3][2];char ss[1110000];
const int mod=1000000007;
int main() {
    int n,k;scanf("%d%d%s",&n,&k,ss+1);
    ss[++n]='X';memset(b,0,sizeof(b));memset(w,0,sizeof(b));
    for(int i=1;i<=n;i++) {
        b[i]=b[i-1];if(ss[i]=='B')b[i]++;
        w[i]=w[i-1];if(ss[i]=='W')w[i]++;
    }
    memset(f,0,sizeof(f));f[0][0][1]=1;
    for(int i=1;i<=n;i++) {
        if(ss[i]!='W')for(int j=0;j<3;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod;
        if(ss[i]!='B')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(ss[i]!='W'&&w[i]==w[i-k]) {
            f[i][1][0]=(f[i][1][0]+f[i-k][0][1])%mod;
            f[i][0][0]=(f[i][0][0]-f[i-k][0][1])%mod;
        }if(ss[i]!='B'&&b[i]==b[i-k]) {
            f[i][2][1]=(f[i][2][1]+f[i-k][1][0])%mod;
            f[i][1][1]=(f[i][1][1]-f[i-k][1][0])%mod;
        }
    }printf("%d\n",((f[n][2][0])%mod+mod)%mod);
    return 0;
}

版权声明
本文为[osc_ 1q5l9zt9]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012071504368615.html