这道题当时做的时候觉得是数论题，包含两个01串什么的，但是算重复的时候又很蛋疼，赛后听说是字符串，然后就觉得很有可能。昨天队友问到这一题，在学了AC自动机之后就觉得简单了许多。那个时候不懂AC自动机，不知道什么是状态，因此没有想到有效的dp方法。
题意是这样的，给定两个RD串，譬如RRD,DDR这样子的串，然后现在要你向右走（R）m步，向下走（D）n步，问有多少种走法能够包含给定的两个串。
一个传统的dp思想是这样的 dp[i][j][x][y][k],表示走了i步R,j步D,x,y表示两个串各匹配了多少各，k表示的是1,2串匹配的一个4进制数（00，01，10，11，你懂的，11表示都匹配了，10表示匹配了1串）。 但是这样一来空间开不下，二来当某个点失配的时候我们不知道当前的x,y会转移到哪里，这个时候很自然的，我们就想到了AC自动机，AC自动机压入两个串只需要不超过串的总长度的结点，而且当我们在自动机上转移的时候，我们可以知道失配的时候转移到哪里。所以重新定义一下就是 dp[i][j][k][x] k表示自动机上的状态，x表示4进制数。转移的时候就考虑由当前的状态dp[i][j][k][x]转移到dp[i+1][j][nxt1][nxtx] dp[i][j+1].... 其中新的状态nxt以及对应的四进制数转移就需要根据AC自动机的失配算出来。 如果预处理出当失配时回到的那个结点感觉可能会更快一些。 我代码里多写了个dfs，主要是预处理了 到达改状态时对应的四进制数，所以转移的时候只需要或一下就可以了。
第一次做AC自动机上的dp然后 1A了，好开心！
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>#include<vector>#include<cmath>#include<queue>#define maxn 2000#define mod 1000000007using
namespace std;struct
Trie{ Trie * go[2]; Trie *fail; int
sta; void
init() { memset(go, 0, sizeof(go)), fail == NULL; sta = 0; }}pool[maxn],*root;int
tot;void
insert(char
*c,int
type){ int
len = strlen(c); Trie *p = root; for
(int i = 0; i < len; i++){ int
ind = c[i] == ‘R‘
? 0 : 1; if
(p->go[ind] != NULL){ p = p->go[ind]; } else{ pool[tot].init(); p->go[ind] = &pool[tot++]; p = p->go[ind]; } } p->sta |= type;}void
getFail(){ queue<Trie*> que; que.push(root); root->fail = NULL; while
(!que.empty()) { Trie *temp = que.front(); que.pop(); Trie *p = NULL; for
(int i = 0; i < 2; i++){ if
(temp->go[i] != NULL){ if
(temp == root) temp->go[i]->fail = root; else{ p = temp->fail; while
(p != NULL){ if
(p->go[i] != NULL){ temp->go[i]->fail = p->go[i]; break; } p = p->fail; } if
(p == NULL) temp->go[i]->fail = root; } que.push(temp->go[i]); } } }}int
dfs(Trie *x){ if
(x == NULL) return
0; return
x->sta |= dfs(x->fail);}int
m, n;int
dp[120][120][240][4];char
str[120];int
main(){ int
T; cin >> T; while
(T--) { tot = 0; root = &pool[tot++]; root->init(); scanf("%d%d", &m, &n); for
(int i = 1; i <= 2; i++){ scanf("%s", str); insert(str, i); } getFail(); for
(int i = 0; i < tot; i++){ dfs(&pool[i]); } for
(int i = 0; i <= m; i++){ for
(int j = 0; j <= n; j++){ for
(int k = 0; k <= tot; k++){ for
(int x = 0; x < 4; x++){ dp[i][j][k][x] = 0; } } } } dp[0][0][0][0] = 1; for
(int i = 0; i <= m; i++){ for
(int j = 0; j <= n; j++){ for
(int k = 0; k < tot; k++){ for
(int x = 0; x < 4; x++){ Trie* p = &pool[k]; if
(p->go[0] != NULL){ (dp[i + 1][j][p->go[0] - pool][x | p->go[0]->sta] += dp[i][j][k][x]) %= mod; } else{ Trie *temp = p->fail; while
(temp != NULL) { if
(temp->go[0] != NULL){ (dp[i + 1][j][temp->go[0] - pool][x | temp->go[0]->sta] += dp[i][j][k][x]) %= mod; break; } temp = temp->fail; } if
(temp == NULL) (dp[i + 1][j][0][x | root->sta] += dp[i][j][k][x]) %= mod; } if
(p->go[1] != NULL){ (dp[i][j + 1][p->go[1] - pool][x | p->go[1]->sta] += dp[i][j][k][x]) %= mod; } else{ Trie *temp = p->fail; while
(temp != NULL) { if
(temp->go[1] != NULL){ (dp[i][j + 1][temp->go[1] - pool][x | temp->go[1]->sta] += dp[i][j][k][x]) %= mod; break; } temp = temp->fail; } if
(temp == NULL) (dp[i][j + 1][0][x | root->sta] += dp[i][j][k][x]) %= mod; } } } } } int
ans = 0; for
(int i = 0; i < tot; i++){ ans = ans + dp[m][n][i][3]; ans %= mod; } printf("%d\n", ans); } return
0;} |
HDU4758 Walk Through Squares AC自动机&&dp,布布扣,bubuko.com
HDU4758 Walk Through Squares AC自动机&&dp
原文：http://www.cnblogs.com/chanme/p/3569669.html