HDU 2825 AC 로봇 + DP
이 비밀번호가 나타날 수 있는 총수를 물어보세요.
사고방식: 우선 AC자동기를 구성한다. m은 매우 작기 때문에 10이다. 우리는 2진법으로 각magic words의 사용 상황을 나타낼 수 있다.
dp[i][j][k]에 대해 길이가 i일 때 j라는 노드와 일치하고 현재 선택한magic words는 k상태일 때의 최대 수량입니다.
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
#define MOD 20090717
#define N 1111111
int n , m , k ;
int cnt ;
struct AC_AUTO {
int next[26] ;
int fail ;
int st ;
void init() {
mem(next ,0) ;
fail = -1 ;
st = 0 ;
}
} a[500000];
int vis[111111] ;
void show(int now) {
vis[now] = 1 ;
cout << now << " " << a[now].fail << endl;
for (int i = 0 ; i < 26 ; i ++ ) {
if(a[now].next[i] != 0 && !vis[a[now].next[i]]) {
show(a[now].next[i]) ;
}
}
}
void insert(char *s,int k) {
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].st |= (1 << k) ;
}
int q[111111] ;
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] = 0 ;
else 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]].st |= a[a[p].next[i]].st ;
break ;
}
p = a[p].fail ;
}
if(p == -1)a[a[front].next[i]].fail = 0 ;
q[tail ++] = a[front].next[i] ;
}
}
}
}
int dp[26][200][1 << 10] ;
int solve() {
for (int i = 0 ; i <= n ; i ++ )
for (int j = 0 ; j <= cnt ; j ++ )
for (int x = 0 ; x <= 1 << m ; x ++ )
dp[i][j][x] = 0 ;
dp[0][0][0] = 1 ;
for (int i = 0 ; i < n ; i ++ )// i
for (int j = 0 ; j < cnt ; j ++ )// j
for (int x = 0 ; x < 1 << m ; x ++) { // x
if(!dp[i][j][x])continue ;
for (int y = 0 ; y < 26 ; y ++ ) { // y
int newj = a[j].next[y] ;
int newst = x | a[newj].st ;
dp[i + 1][newj][newst] = (dp[i][j][x] + dp[i + 1][newj][newst] ) % MOD ;
}
}
int ans = 0 ;
for (int i = 0 ; i < 1 << m ; i ++ ) {
int ret = 0 ;
int d = i ;
for (; d ; d -= d & (-d) , ret ++) ;
if(ret < k )continue ;
for (int j = 0 ; j < cnt ; j ++ ) {
ans = (ans + dp[n][j][i]) % MOD ;
}
}
return ans ;
}
char in[111] ;
int main() {
while(cin >> n >> m >> k, (n + m + k)) {
a[0].init() ;
cnt = 1 ;
for (int i = 0 ; i < m ; i ++ ) {
scanf("%s",in) ;
insert(in , i) ;
}
ac_bfs() ;
printf("%d
",solve()) ;
}
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.