题目意思 就是给你 N 个字符 去组成 M 长的单词有多少种方法是 不包含病毒串的 病毒串有 p 个
方法 恶心啊! 这题 是 DP 的经典题目了,因为所有的字符 可以看成是 单词中的后缀 在 着 p 个病毒中 都是没有一点点匹配的 比如说 abcdefg 这个字符,病毒有 hij,sek,ac 等等,你看字符是不是后缀都没有匹配到p个单词前缀的任意位置前缀,放在root ,然后,对每个就是有匹配的字符了,比如说 abcdehi ,abcdehh 等等,那么他的全集就是所有可能的结果了;
然后就是 dp 的部分 dp 部分倒是很好理解;依据节点数分类; 坑爹的,这题目还附加了一个大数,结果 太大了 ;;;; 这不玩人么; 还有所有字符的情况,我觉得还是自己写个 hash 好吧!! 安全啊。。。。
#include<iostream> #include<stdio.h> #include<cstring> #include<algorithm> using namespace std; structdate { date *next[60],*fail; int flag,in; }arr[121],*que[121],*root; char str[60],cha[60]; int tail,head,total,N,M,P,hash[256]; date *creat_node( ) { for( int i = 0; i < N; ++i ) arr[total].next[i] = NULL; arr[total].fail = NULL; arr[total].flag = 0; arr[total].in = total; return &arr[total++]; } void inint( ) { tail = head = total = 0; root = creat_node(); root->fail = root; } void insert( char *word ) { date *temp = root; while( *word ) { int num = hash[int(*word)]; if( temp->next[num] == NULL ) temp->next[num] = creat_node( ); temp = temp->next[num]; word++; } temp->flag = true; } void build_AC( ) { que[tail++] = root; while( tail > head ) { date *temp = que[head++]; for( int i = 0; i < N; i++ ) if( temp->next[i] != NULL ) { if( temp == root ) temp->next[i]->fail = root; else temp->next[i]->fail = temp->fail->next[i]; temp->next[i]->flag |= temp->next[i]->fail->flag; que[tail++] = temp->next[i]; } else { if( temp == root ) temp->next[i] = root; else temp->next[i] = temp->fail->next[i]; } } } int dp[55][256][100]; void add_value( int *dt,int *ds ) { int t = 0; for( int i = 0; i <= 90; i++ ){ t = dt[i] + ds[i] + t; dt[i] = t%10; t /= 10; } } void DP( ) { int i,j,k; memset(dp,0,sizeof(dp)); dp[0][0][0] = 1; for( i = 1; i <= M; i++ ) for( j = 0; j < total;j++ ) for( k = 0; k < N; k++ ) if( !arr[j].next[k]->flag ) add_value( dp[i][arr[j].next[k]->in],dp[i-1][j] ); for( i = 0; i < total; i++ ) add_value( dp[M+1][0],dp[M][i] ); bool fell = false; for( i = 90; i >= 0; i-- ) if( dp[M+1][0][i] ) { while( i >= 0 )printf("%d",dp[M+1][0][i]),i--; fell = true; } if( !fell )printf("0"); printf("\n"); } int main( ) { while( scanf("%d%d%d",&N,&M,&P) != EOF ) { inint( ); cin>>str; for( int i = 0; i < N ; ++i ) hash[str[i]] = i; for( int i = 1; i <= P; i++ ) cin>>cha,insert( cha ); build_AC( ); DP( ); } return 0; }