果然清華集訓的題目。。。顯然的DP題但是不會做。。。

我們令f[i][j][w]表示狀態方程

w表示到了字符串的第w個

i = 0, 1, 2分別表示k個B和k個W都沒填上、k個B填上了k個W沒填上、k個B和k個W都填上了三種狀態

j = 0, 1分別表示第w位上填B/W

于是方程就比較容易列出來了，注意要用到容斥原理

?

1 /************************************************************** 2 Problem: 2958 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:652 ms 7 Memory:33032 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 12 using namespace std; 13 const int N = 1000005; 14 const int mod = 1e9 + 7; 15 16 int n, k; 17 char st[N]; 18 int s0[N], s1[N], f[3][2][N]; 19 20 void read_in() { 21 int i; 22 char ch = getchar(); 23 while (ch != 'W' && ch != 'B' && ch != 'X') 24 ch = getchar(); 25 for (i = 1; i <= n; ++i) 26 st[i] = ch, ch = getchar(); 27 } 28 29 inline int calc(char c, int *s, int i, int t) { 30 if (i < k || st[i - k] == c || s[i] - s[i - k]) return 0; 31 return f[t - 1][i == k ? 0 : 2 - t][i - k]; 32 } 33 34 int main() { 35 int i; 36 scanf("%d%d", &n, &k); 37 read_in(); 38 f[0][0][0] = 1; 39 for (i = 1; i <= n; ++i) { 40 s0[i] = s0[i - 1] + (st[i] == 'W'); 41 s1[i] = s1[i - 1] + (st[i] == 'B'); 42 if (st[i] != 'W') { 43 f[0][0][i] = (0ll + f[0][1][i - 1] + f[0][0][i - 1] - calc('B', s0, i, 1) + mod) % mod; 44 f[1][0][i] = (0ll + f[1][0][i - 1] + f[1][1][i - 1] + calc('B', s0, i, 1)) % mod; 45 f[2][0][i] = (0ll + f[2][0][i - 1] + f[2][1][i - 1]) % mod; 46 } 47 if (st[i] != 'B') { 48 f[0][1][i] = (0ll + f[0][1][i - 1] + f[0][0][i - 1]) % mod; 49 f[1][1][i] = (0ll + f[1][0][i - 1] + f[1][1][i - 1] - calc('W', s1, i, 2) + mod) % mod; 50 f[2][1][i] = (0ll + f[2][0][i - 1] + f[2][1][i - 1] + calc('W', s1, i, 2)) % mod; 51 } 52 } 53 printf("%d\n", (f[2][0][n] + f[2][1][n]) % mod); 54 return 0; 55 } View Code

(p.s. Orz 江哥...)

轉載于:https://www.cnblogs.com/rausen/p/4264103.html

總結

以上是生活随笔為你收集整理的BZOJ2958 序列染色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。