bzoj2958: 序列染色(DP)

2958: 序列染色

题解：
　　大难题啊（还是我太菜了）
代码：
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define mod 1000000007
 7 using namespace std;
 8 typedef long long LL;
 9 int n,k;
10 int sb[1110000],sw[1110000];
11 LL f[1110000][3][3];//前i位状态为j第i为为k的方案数 (k=0 为B k=1 为w)
12 //j==0 没有k个B和k个W
13 //j==1 只有k个B
14 //j==2 有k个B和k个W
15 char st[1110000];
16 int main()
17 {
18     scanf("%d%d",&n,&k);scanf("%s",st+1);
19     memset(sb,0,sizeof(sb));memset(sw,0,sizeof(sw));
20     for(int i=1;i<=n;i++)
21     {
22         sb[i]=sb[i-1];sw[i]=sw[i-1];
23         if(st[i]=='B')sb[i]++;
24         else if(st[i]=='W')sw[i]++;
25     }
26     memset(f,0,sizeof(f));
27     f[0][0][1]=1;//B在左边所以先放个W... 
28     for(int i=1;i<=n;i++)
29     {
30         if(st[i]!='W')for(int j=0;j<=2;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1]+mod)%mod;
31         if(st[i]!='B')for(int j=0;j<=2;j++)f[i][j][1]=(f[i-1][j][0]+f[i-1][j][1]+mod)%mod;
32         if(i<k)continue;
33         if(st[i]!='W' && sw[i]==sw[i-k])
34         {
35             f[i][1][0]=(f[i][1][0]+f[i-k][0][1]+mod)%mod;
36             f[i][0][0]=(f[i][0][0]-f[i-k][0][1]+mod)%mod;
37         }
38         if(st[i]!='B' && sb[i]==sb[i-k])
39         {
40             f[i][2][1]=(f[i][2][1]+f[i-k][1][0]+mod)%mod;
41             f[i][1][1]=(f[i][1][1]-f[i-k][1][0]+mod)%mod;
42         }
43     }
44     printf("%lld
",(f[n][2][0]+f[n][2][1]+mod)%mod);
45     return 0;
46 }