題面

　　Bzoj1559

解析

　　?要求一個能包含所有字符串的串的個數(shù)，聯(lián)想到AC自動機。

　　每一個節(jié)點需要存一個終點信息，即以這個點為結尾的字符串編號，這個需要開一個vector來存，因為一個節(jié)點需要繼承fail節(jié)點所含的終點信息。

　　再看一下數(shù)據(jù)規(guī)模，發(fā)現(xiàn)很小，于是可以用一個維度記錄狀態(tài)進行狀壓DP，設$dp[x][len][i]$為當前從自動機的第x號節(jié)點開始，當前狀態(tài)為i(二進制下，第j位為1/0，1表示包含第j+1個字符串，0表示不包含)的長為len的合法字符串個數(shù)，顯然可以記憶化搜索(當然其本質還是狀壓dp), 答案就是$dp[0][l][0]$。

　　但如果每次都要跳fail指針的話顯然不劃算，于是建成trie圖，即補全的AC自動機，在圖上記憶化搜索。

　　在$dp[0][l][0] <= 42$時需要按字典序輸出字符串，當然是按照貪心的原則，并且防止走冤枉路，能走小的就走小的，不然就不走，但什么時候是能走的呢？設需要判斷的節(jié)點為x，到達x時的狀態(tài)為i，到達x后還剩長度為len的字符串，如果$dp[x][len][i] > 0$, 就走，否則不走。

　代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<queue> using namespace std; typedef long long ll;int l, n, tot, fail[105], go[105][30]; char s[15], stak[15]; ll dp[105][30][1<<10]; vector<int> G[105];void Add(int x) {int now = 0;int len = strlen(s);for(int i = 0; i < len; ++i){if(!go[now][s[i]-'a'])go[now][s[i]-'a'] = ++tot;now = go[now][s[i]-'a'];}G[now].push_back(x); }queue<int> q;void Getfail() {for(int i = 0; i < 26; ++i)if(go[0][i])q.push(go[0][i]);while(!q.empty()){int st = q.front();q.pop();for(int i = 0 ; i < 26; ++i)if(go[st][i]){q.push(go[st][i]);int t = fail[st];while(t && !go[t][i]) t = fail[t];fail[go[st][i]] = go[t][i];for(unsigned int j = 0; j < G[go[t][i]].size(); ++j){int id = G[go[t][i]][j];G[go[st][i]].push_back(id);}}elsego[st][i] = go[fail[st]][i];} }ll dfs(int x, int rest, int stu) {if(dp[x][rest][stu] != -1) return dp[x][rest][stu];if(rest == 0){if(stu == (1<<n) - 1)return dp[x][rest][stu] = 1;elsereturn dp[x][rest][stu] = 0;}ll ret = 0;for(int i = 0; i < 26; ++i){int to = go[x][i];int nxt = stu;for(unsigned int j = 0; j < G[to].size(); ++j){int id = G[to][j];nxt |= (1<<(id-1));}ret += dfs(to, rest - 1, nxt);}return dp[x][rest][stu] = ret; }void write(int x, int rest, int stu) {if(rest == 0){printf("%s", stak+1);printf("\n");return;}for(int i = 0; i < 26; ++i){int to = go[x][i];int nxt = stu;for(unsigned int j = 0; j < G[to].size(); ++j){int id = G[to][j];nxt |= (1<<(id-1));}if(dp[to][rest-1][nxt] > 0){stak[l-rest+1] = i + 'a';write(to, rest - 1, nxt);}} }int main() {scanf("%d%d", &l, &n);for(int i = 1; i <= n; ++i){scanf("%s", s);Add(i);}Getfail();memset(dp, -1, sizeof(dp));dfs(0, l, 0);printf("%lld\n", dp[0][l][0]);if(dp[0][l][0] <= 42)write(0, l, 0);return 0; } View Code

?

轉載于:https://www.cnblogs.com/Joker-Yza/p/11333677.html

總結

以上是生活随笔為你收集整理的[JSOI2009]密码——AC自动机+记忆化搜索(状压)的全部內容，希望文章能夠幫你解決所遇到的問題。

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