题面

传送门

思路

首先，有一个非常显然的思路就是dp：

设$dp[i][j]$表示前i个字符，最后一个为j

然后发现这个东西有后效性

改！设$dp[i][j]$代表前i个字符，最后15个的状态为j（压缩一下），转移的是候枚举增加那个字符，然后看从谁可以推过来

然后就TLE了，完全无压力

怎么优化这个算法？

显然，枚举完增加哪个字符以后，可以用AC自动机来实现多模匹配

然后发现：我们把j的定义变成AC自动机上面的点j，这样一个点就代表一种状态，状态之间互相不重复，而且也没有后效性

这样的定义方法还有一个好处：状态少，从$3^{15}$个变成了$300$个

于是我们得到最终做法：

最终算法

对于输入的模板串建立AC自动机

令$dp[i][j]$表示前i个字符，最后一个字符跑到AC自动机的第j位上的最大答案

于是我们只要对于每个$dp[i][j]$枚举下一个是A,B,C,转移到下一个节点j'，然后跳一遍fail指针

对于匹配到的一个长度为k的模板串，$dp[i+1][j']=max\left(dp[i+1][j'],dp[i-k][j]\right)$

最后答案就是$dp[K][i]$的最大值

Code

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node{int num,fail,son[3];node(){num=fail=0;memset(son,0,sizeof(son));} }a[510];int cnt; void add(char s[]){//插入字符串到trieint len=strlen(s),i,cur=0;for(i=0;i<len;i++){if(!a[cur].son[s[i]-'A']) a[cur].son[s[i]-'A']=++cnt;cur=a[cur].son[s[i]-'A'];}a[cur].num++; } void getfail(){//bfs求fail指针int u,v,q[510],head=0,tail=0,i;for(i=0;i<3;i++){if(!a[0].son[i]) continue;a[0].fail=0;q[tail++]=a[0].son[i];}while(head<tail){u=q[head++];for(i=0;i<3;i++){v=a[u].son[i];if(v) a[v].fail=a[a[u].fail].son[i],q[tail++]=v;else a[u].son[i]=a[a[u].fail].son[i];}} } int m,n,dp[1010][510];bool vis[1010][510]; int proc(int cur,int val){//跳fail指针求值while(cur) val+=a[cur].num,cur=a[cur].fail;return val; } int main(){scanf("%d%d",&m,&n);int i,j,k,tmp;char s[20];for(i=1;i<=m;i++) scanf("%s",s),add(s);getfail();vis[0][0]=1;for(i=0;i<n;i++){for(j=0;j<=cnt;j++){if(!vis[i][j]) continue;for(k=0;k<3;k++){tmp=a[j].son[k];dp[i+1][tmp]=max(dp[i+1][tmp],proc(tmp,dp[i][j]));vis[i+1][tmp]=1;}}}int ans=0;for(i=0;i<=cnt;i++) ans=max(ans,dp[n][i]);printf("%d\n",ans); }

转载于:https://www.cnblogs.com/dedicatus545/p/8907126.html

总结

以上是生活随笔为你收集整理的[USACO12Jan][luogu3041] Video Game Combos [AC自动机+dp]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。