---

題目描述

貝西在玩電腦游戲！在游戲中，鍵盤的’A’,’B’和’C’三個按鍵是唯一可用的。貝西可以根據(jù)她的需要隨意按這幾個鍵。但是游戲里只有N(1 <= N<= 20)種招式。一個招式命令就是由‘A’,’B’,’C’三個按鍵構(gòu)成的一個長度在1到15間的按鍵組合。

當(dāng)貝西按出了一個招式命令，她會得到1分。多個招式可以同時重疊使用。比如當(dāng)N=3時，有3個招式命令”ABA”,”CB”,和”ABACB”.
但貝西按下”ABACB”時，她將得到3分。

貝西想盡可能多得分，如果她總共按了K(1 <= K <= 1,000)次按鍵,她能得到的最大得分是多少？

---

輸入格式

第一行，兩個空格間隔的整數(shù)N 和 K
接下來N行，每行表示一個招式命令

---

輸出格式

輸出一個整數(shù)，表示最大得分。

---

樣例數(shù)據(jù)

樣例輸入

3 7
ABA
CB
ABACB

樣例輸出

4

樣例說明

按鍵順序是ABACBCB, 得到4分
ABA1分，ABACB分, CB2分。

---

題目分析

做完poj1625再做這些題感覺好水啊！
建立AC自動機方式同poj1625，只是將危險結(jié)點標(biāo)記傳遞改成了數(shù)目相加->見代碼
f[i,j]表示root->j長度為i的鏈上最多的combo數(shù)

---

源代碼

#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構(gòu)造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]; //如果存在滿足條件的點則設(shè)置失敗指針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; }

---

總結(jié)

以上是生活随笔為你收集整理的[USACO 2012 January Gold] Video Game Combos的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。