---

题目描述

贝西在玩电脑游戏！在游戏中，键盘的’A’,’B’和’C’三个按键是唯一可用的。贝西可以根据她的需要随意按这几个键。但是游戏里只有N(1 <= N<= 20)种招式。一个招式命令就是由‘A’,’B’,’C’三个按键构成的一个长度在1到15间的按键组合。

当贝西按出了一个招式命令，她会得到1分。多个招式可以同时重叠使用。比如当N=3时，有3个招式命令”ABA”,”CB”,和”ABACB”.
但贝西按下”ABACB”时，她将得到3分。

贝西想尽可能多得分，如果她总共按了K(1 <= K <= 1,000)次按键,她能得到的最大得分是多少？

---

输入格式

第一行，两个空格间隔的整数N 和 K
接下来N行，每行表示一个招式命令

---

输出格式

输出一个整数，表示最大得分。

---

样例数据

样例输入

3 7
ABA
CB
ABACB

样例输出

4

样例说明

按键顺序是ABACBCB, 得到4分
ABA1分，ABACB分, CB2分。

---

题目分析

做完poj1625再做这些题感觉好水啊！
建立AC自动机方式同poj1625，只是将危险结点标记传递改成了数目相加->见代码
f[i,j]表示root->j长度为i的链上最多的combo数

---

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() {int num=0,bj=1;char x=getchar();while(x<'0'||x>'9') {if(x=='-')bj=-1;x=getchar();}while(x>='0'&&x<='9') {num=num*10+x-'0';x=getchar();}return num*bj; } const int maxn=30000; struct Tree {int child[26],fail,tot; //fail失败指针void clear() {memset(child,0,sizeof(child));fail=0;tot=0;} }; int root=1; struct Aho_Corasick_Automaton { //AC自动机int cnt;Tree tree[maxn];void init() {cnt=1;memset(tree,0,sizeof(tree));}void insert(string s) {int now=root,len=s.length();for(int i=0; i<len; i++) {int j=s[i]-'A';if(!tree[now].child[j]) {tree[++cnt].clear();tree[now].child[j]=cnt;}now=tree[now].child[j];}tree[now].tot++;}void buildfail() { //Bfs构造Fail指针queue<int>Q;Q.push(root);while(!Q.empty()) {int Now=Q.front();Q.pop();for(int i=0; i<3; i++) {int Next=tree[Now].child[i];if(Next==0) { //儿子不存在if(tree[tree[Now].fail].child[i])tree[Now].child[i]=tree[tree[Now].fail].child[i];else tree[Now].child[i]=root;continue;}Q.push(Next);int fatherfail=tree[Now].fail; //父亲的失败指针while(fatherfail&&!tree[fatherfail].child[i])fatherfail=tree[fatherfail].fail; //寻找可退回点if(fatherfail)tree[Next].fail=tree[fatherfail].child[i]; //如果存在满足条件的点则设置失败指针else tree[Next].fail=root; //否则指回roottree[Next].tot+=tree[tree[Next].fail].tot;}}} }; Aho_Corasick_Automaton ac; int n,k,f[1005][3005],ans=-0x7fffffff/2; int main() {ios::sync_with_stdio(false);cin>>n>>k;ac.init();for(int i=1; i<=n; i++) {string s;cin>>s;ac.insert(s);}ac.buildfail();memset(f,-0x7f,sizeof(f));f[0][1]=0;for(int i=1; i<=k; i++)for(int j=1; j<=ac.cnt; j++)for(int k=0; k<3; k++)f[i][ac.tree[j].child[k]]=max(f[i][ac.tree[j].child[k]],f[i-1][j]+ac.tree[ac.tree[j].child[k]].tot);for(int i=1; i<=ac.cnt; i++)ans=max(ans,f[k][i]);cout<<ans<<endl;return 0; }

---

总结

以上是生活随笔为你收集整理的[USACO 2012 January Gold] Video Game Combos的全部内容，希望文章能够帮你解决所遇到的问题。

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