【Luogu3041】视频游戏的连击（AC自动机，动态规划）

题面链接

题解

首先构建出AC自动机

然后在AC自动机上面跑DP

转移很显然从Trie树的节点跳到他的儿子节点

但是要注意一个问题，

在计算的时候，每一个节点加入后能够

造成的贡献

要加上他的子串的贡献

至于DP：

设f[i][j]表示已经使用了i个字母

当前在Trie树的第j个节点上面能够产生的最大贡献

很显然，转移到他的儿子节点上面，同时统计贡献即可

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 1000000
int N,K;
int tot=0,ans;
char s[20];
int f[1100][400];
struct Node
{int vis[3];int p;int fail;
}t[5000];
void Add(char *s)
{int l=strlen(s);int now=0;for(int i=0;i Q;for(int i=0;i<3;++i)if(t[0].vis[i])Q.push(t[0].vis[i]);while(!Q.empty()){int u=Q.front();Q.pop();for(int i=0;i<3;++i){if(t[u].vis[i]){t[t[u].vis[i]].fail=t[t[u].fail].vis[i];Q.push(t[u].vis[i]);}elset[u].vis[i]=t[t[u].fail].vis[i];}t[u].p+=t[t[u].fail].p;}
}
void DP()
{for(int T=0;T<=K;++T)for(int i=1;i<=tot;++i)f[T][i]=-INF;for(int T=1;T<=K;++T)for(int i=0;i<=tot;++i)for(int j=0;j<3;++j)f[T][t[i].vis[j]]=max(f[T][t[i].vis[j]],f[T-1][i]+t[t[i].vis[j]].p);for(int i=0;i<=tot;++i)ans=max(ans,f[K][i]);
}
int main()
{scanf("%d%d",&N,&K);for(int i=1;i<=N;++i){scanf("%s",s);Add(s);}Build();DP();printf("%d
",ans);return 0;
}