bzoj2958: 序列染色(DP)

2958: 序列染色

题目：传送门

---

题解：

　　 大难题啊（还是我太菜了）

　　 %一发大佬QTT

　　

---

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define mod 1000000007

 using namespace std;

 typedef long long LL;

 int n,k;

 int sb[],sw[];

 LL f[][][];//前i位状态为j第i为为k的方案数 (k=0 为B k=1 为w)

 //j==0 没有k个B和k个W

 //j==1 只有k个B

 //j==2 有k个B和k个W

 char st[];

 int main()

 {

     scanf("%d%d",&n,&k);scanf("%s",st+);

     memset(sb,,sizeof(sb));memset(sw,,sizeof(sw));

     for(int i=;i<=n;i++)

     {

         sb[i]=sb[i-];sw[i]=sw[i-];

         if(st[i]=='B')sb[i]++;

         else if(st[i]=='W')sw[i]++;

     }

     memset(f,,sizeof(f));

     f[][][]=;//B在左边所以先放个W...

     for(int i=;i<=n;i++)

     {

         if(st[i]!='W')for(int j=;j<=;j++)f[i][j][]=(f[i-][j][]+f[i-][j][]+mod)%mod;

         if(st[i]!='B')for(int j=;j<=;j++)f[i][j][]=(f[i-][j][]+f[i-][j][]+mod)%mod;

         if(i<k)continue;

         if(st[i]!='W' && sw[i]==sw[i-k])

         {

             f[i][][]=(f[i][][]+f[i-k][][]+mod)%mod;

             f[i][][]=(f[i][][]-f[i-k][][]+mod)%mod;

         }

         if(st[i]!='B' && sb[i]==sb[i-k])

         {

             f[i][][]=(f[i][][]+f[i-k][][]+mod)%mod;

             f[i][][]=(f[i][][]-f[i-k][][]+mod)%mod;

         }

     }

     printf("%lld\n",(f[n][][]+f[n][][]+mod)%mod);

     return ;

 }