[JSOI2009]密码——AC自动机+记忆化搜索(状压)
题面 Bzoj1559 解析 ?要求一个能包含所有字符串的串的个数,联想到AC自动机。 每一个节点需要存一个终点信息,即以这个点为结尾的字符串编号,这个需要开一个vector来存,因为一个节点需要继承fail节点所含的终点信息。 再看一下数据规模,发现很小,于是可以用一个维度记录状态进行状压DP,设$dp[x][len][i]$为当前从自动机的第x号节点开始,当前状态为i(二进制下,第j位为1/0,1表示包含第j+1个字符串,0表示不包含)的长为len的合法字符串个数,显然可以记忆化搜索(当然其本质还是状压dp),答案就是$dp[0][l][0]$。 但如果每次都要跳fail指针的话显然不划算,于是建成trie图,即补全的AC自动机,在图上记忆化搜索。 在$dp[0][l][0] <= 42$时需要按字典序输出字符串,当然是按照贪心的原则,并且防止走冤枉路,能走小的就走小的,不然就不走,但什么时候是能走的呢?设需要判断的节点为x,到达x时的状态为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); } } else go[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; else return 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 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("%lldn",dp[0][l][0]); if(dp[0][l][0] <= 42) write(0,0); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |