HDU 2825 Wireless Password(AC 로봇 + 섀시 DP)
4069 단어 password
AC 자동기를 구축하여 검색을 진행하는데 dp[i][j][k]는 문자열의 길이가 i이고 사전 트리의 j번째 노드와 일치하며 k개의magic word와 일치할 때의 총수를 나타낸다.
전이 방정식은 (dp[i+1][j의 아들][k|j의 아들의 상태]+=dp[i][j][k])%mod이다.
주의해야 할 것은 단어는 중복 사용이 가능하기 때문에 단어의 끝에fail은 루트가 가리키는 각 노드를 가리킨다
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>// INT_MAX
#define MAX 100005
#define mod 20090717
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x << 1
#define R(x) x << 1 | 1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///
using namespace std;
struct Trie {
int next[26] ;
int fail ;
int buff ;
void init() {
memset(next,0,sizeof(next)) ;
fail = -1 ;
buff = 0 ;
}
} a[111];
int cnt,n,m,K;
int q[111] , dp[30][111][1 << 10];
char keyword[22];
void insert(char *s,int pos) {
int p = 0 ;
for(int i = 0 ; s[i] ; i ++) {
int t = s[i] - 'a' ;
if(a[p].next[t] == 0) {
a[cnt].init();
a[p].next[t] = cnt ++;
}
p = a[p].next[t] ;
}
a[p].buff = 1 << pos;
}
void ac_bfs() {
int i,head = 0,tail = 0;
q[tail ++] = 0;
while(head < tail) {
int front = q[head ++];
for(i = 0; i < 26 ; i ++) {
if(a[front].next[i] == 0) {
if(front != 0) a[front].next[i] = a[a[front].fail].next[i];
} else {
int p = a[front].fail ;
while(p != -1) {
if(a[p].next[i] != 0) {
a[a[front].next[i]].fail = a[p].next[i] ;
a[a[front].next[i]].buff |= a[a[p].next[i]].buff;// , fail magic word , magic word
break ;
}
p = a[p].fail ;
}
if(p == -1) a[a[front].next[i]].fail = 0 ;
q[tail ++] = a[front].next[i] ;
}
}
}
}
int calone(int x) {
int cal = 0;
while(x) {
if(x & 1) cal ++;
x = x >> 1;
}
return cal;
}
void solve() {
dp[0][0][0] = 1;
int total = 1 << m;
for(int i=0; i<n; i++) {
for(int j=0; j<cnt; j++) {
for(int k=0; k<total; k++) {
if(dp[i][j][k] == 0) continue;
for(int l=0; l<26; l++) {
int buff = a[a[j].next[l]].buff;
dp[i+1][a[j].next[l]][k | buff] = (dp[i+1][a[j].next[l]][k | buff] + dp[i][j][k]) % mod;
}
}
}
}
int ans = 0;
for(int j=0; j<cnt; j++) {
for(int k=0; k<total; k++) {
if(calone(k) < K) continue;
ans = (ans + dp[n][j][k] ) % mod;
}
}
printf("%d
",ans);
}
int main() {
while(scanf("%d%d%d",&n,&m,&K)) {
if(n == 0 && m == 0 && K == 0) break;
a[0].init();
cnt = 1;
for(int i=0; i<m; i++) {
scanf("%s",keyword);
insert(keyword,i);
}
ac_bfs();
for(int i=0; i<=n; i++) {
for(int j=0; j<cnt; j++) {
for(int l=0; l<(1<<m); l++) {
dp[i][j][l] = 0;
}
}
}
solve();
}
return 0;
}
현재 dp의 사고방식과 영감이 부족하다.다른 사람의 생각대로 두드렸는데...어떤 부분은 여전히 해결해야 한다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
MySQL의 루트 암호를 잊었다! 때의 대처법(Windows)평소부터 사용하고 있으면 좋지만 가끔 생각나는 것처럼 사용하기 때문에 그때마다 root 패스워드를 잊어 MySQL에 로그인할 수 없다. MySQL 5.7 서비스에서 실행 명령 줄에서 mysql --version를 입...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.