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 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
IBM Cloud VRA config-sync를 사용하여 비밀번호를 동기화하는 방법IBMCloud에서 네트워크 어플라이언스로 자주 사용되는 VRA 장비에 대한 기사입니다. 중복 구성으로 이용하고 있는 VRA 2대에의 로그인을 같은 패스워드로 넣도록 하고 싶다고 하는 목적하에서, Password 동...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.