AC自动机专题:dp,巧妙的状态定义-HDU3341

题目大意:

给你一个只含"AGCT"四种字符的长度为 n($n\le 40$)的字符串S.然后给m($m\le 50$)个长度小于等于10的匹配串。你现在可以重新排列S使得这m个匹配串在其中出现的次数最多.输出这个次数.

题目思路:

建AC自动机后

其实不难想到一个朴素的转移方程:$dp(a_0,a_1,a_2,a_3,pos)$代表字符串S还剩下 $a_0$个A , $a_1$个G , $a_2$个C , $a_3$个T 且当前在Trie图中的节点为$pos$的出现最多次数。

但是问题是A,G,C,T都可能出现40次。这里我就蠢了。因为 A+G+C+T=40.所以根据均值不等式,状态数最多为: $10^4=10000$ 种。而不是$40^4$了. 这样我们就必须给状态编号.然后直接刷表法dp即可。

AC代码：

#include<bits/stdc++.h> using namespace std; const int maxn = 500 + 5; int ha[42][42][42][42] , num[10] , cnt , dp[14641][505] , bk[1005]; struct S { int a[4]; }sta[14641]; namespace AC{ int tr[maxn][5] , tot; int fail[maxn] , v[maxn]; void init () { tot = 0; for (int i = 0 ; i < maxn ; i++){ for (int j = 0 ; j < 4 ; j++) tr[i][j] = 0; fail[i] = v[i] = 0; } } void add (char * s){ int u = 0; for (int i = 1 ; s[i] ; i++){ if (!tr[u][bk[s[i]]]) tr[u][bk[s[i]]] = ++tot; u = tr[u][bk[s[i]]]; } v[u]++; } queue<int>q; void build (){ while (q.size()) q.pop(); for (int i = 0 ; i < 4 ; i++) if (tr[0][i]) q.push(tr[0][i]); while (q.size()){ int u = q.front();q.pop(); for (int i = 0 ; i < 4 ; i++){ if (tr[u][i]){ fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); }else { tr[u][i] = tr[fail[u]][i]; } } v[u] += v[fail[u]]; } } } char tmp[15] , s[1005]; int main() { int n; bk['A'] = 0; bk['G'] = 1; bk['C'] = 2; bk['T'] = 3; int t = 0; while ( scanf("%d" , &n) , n ){ AC::init(); for (int i = 1 ; i <= n ; i++){ scanf("%s" , tmp + 1); AC::add(tmp); } AC::build(); scanf("%s" , s + 1); memset(num , 0 , sizeof num); for (int i = 1 ; s[i] ; i++) num[bk[s[i]]]++; cnt = 0; for (int i = 0 ; i <= num[0] ; i++) for (int j = 0 ; j <= num[1] ; j++) for (int k = 0 ; k <= num[2] ; k++) for (int l = 0 ; l <= num[3] ; l++){ ha[i][j][k][l] = cnt++ , sta[cnt - 1].a[0] = i , sta[cnt - 1].a[1] = j , sta[cnt - 1].a[2] = k , sta[cnt - 1].a[3] = l; for (int gg = 0 ; gg <= AC::tot ; gg++) dp[cnt - 1][gg] = -1; } dp[ha[num[0]][num[1]][num[2]][num[3]]][0] = 0; for (int i = cnt - 1 ; i > 0 ; i--){ for (int j = 0 ; j <= AC::tot ; j++){ if (dp[i][j] == -1) continue; for (int k = 0 ; k < 4 ; k++){ if (sta[i].a[k] == 0) continue; sta[i].a[k]--; int ni = ha[sta[i].a[0]][sta[i].a[1]][sta[i].a[2]][sta[i].a[3]] , nj = AC::tr[j][k]; dp[ni][nj] = max (dp[ni][nj] , dp[i][j] + AC::v[nj]); sta[i].a[k]++; } } } int ans = 0; for (int i = 0 ; i <= AC::tot ; i++) if (dp[0][i] != -1) ans = max (ans , dp[0][i]); printf("Case %d: %d\n" , ++t , ans); } return 0; }