本文共 1863 字，大约阅读时间需要 6 分钟。
这个题目是老师添加到我们学校的oj上的，估计数据是改过了的吧。题意大概是给了n个串，让你构造出来一个长度不超过k的串，使得这n个串在构造出来的这个串中出现次数最大。这也是我的ac自动机+dp第一题。虽然理解的还不是那么透，但还是做出来了，之前因为dp数组开的过小，wa了好多遍。感觉dp跟ac自动机结合在一起，dp也不显得那么难了。
ac代码：
#include #include #include #include #include #include #include #include #include using namespace std;const int maxn=25;const int maxnum=1010;char s[maxn][maxn];int dp[maxnum][maxnum],n,k,line;struct node{ int cnt; int index; node *fail; node *next[3];}memory[1000000];node *que[maxnum];node *createnode(){ node *p=&memory[line]; for(int i=0;i<3;i++) p->next[i]=NULL; p->cnt=0; p->fail=NULL; p->index=line++; return p;}class AC{ public : node *root; AC() { root=NULL; } void insert(char *str) { int len=strlen(str); if(!root) root=createnode(); node *loca=root; for(int i=0;i next[num]==NULL) loca->next[num]=createnode(); loca=loca->next[num]; } loca->cnt++; } void build() { std::queue s; while(!s.empty()) s.pop(); s.push(root); root->fail=NULL; while(!s.empty()) { node *loca=s.front(); s.pop(); for(int i=0;i<3;i++) { if(loca->next[i]!=NULL) { if(loca==root) loca->next[i]->fail=root; else { node *tmp=loca->fail; while(tmp!=NULL) { if(tmp->next[i]!=NULL) { loca->next[i]->fail=tmp->next[i]; break; } tmp=tmp->fail; } if(tmp==NULL) loca->next[i]->fail=root; } if(loca->next[i]->fail->cnt) loca->next[i]->cnt+=loca->next[i]->fail->cnt; s.push(loca->next[i]); } else if(loca==root) loca->next[i]=root; else loca->next[i]=loca->fail->next[i]; } } } int DP() { memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=0;i index; if(dp[i][j]+memory[num].cnt>dp[i+1][num]) dp[i+1][num]=dp[i][j]+memory[num].cnt; } } } int ans=0; for(int i=0;i<=k;i++) { for(int j=0;j
之后会陆续放上这一类的题目。
转载于:https://www.cnblogs.com/RainingDays/archive/2012/11/20/2779689.html
View Code