傳送門

SPOJ10502

Luogu3041

Description

Bessie is playing a video game! In the game, the three letters ‘A’, ‘B’,and ‘C’ are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only N distinct combos possible (1 <= N<= 20). Combo i is represented as a string S_i which has a length between 1 and 15 and contains only the letters ‘A’, ‘B’, and ‘C’.
Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if N = 3 and the three possible combos are “ABA”, “CB”, and “ABACB”, and Bessie presses “ABACB”, she will end with 3 points. Bessie may score points for a single combo more than once.
Bessie of course wants to earn points as quickly as possible. If she presses exactly K buttons (1 <= K <= 1,000), what is the maximum number of points she can earn?
給你個模式串（每個長度≤15，1≤N≤20），串中只含有“ABC”三種字母。求一長度為K（1≤K≤1000）的字符串，使得匹配數最大（重復匹配計多次），輸出最大值。

Input

• Line 1: Two space-separated integers: N and K.
• Lines 2..N+1: Line i+1 contains only the string S_i, representing combo i.

Output

• Line 1: A single integer, the maximum number of points Bessie can obtain.

Sample Input

3 7
ABA
CB
ABACB

Sample Output

4

Hint

The optimal sequence of buttons in this case is ABACBCB, which gives 4 points–1 from ABA, 1 from ABACB, and 2 from CB.

Solution

• AC自動機模板+DP
• val[u]表示后綴樹上u及其子孫中危險節點總和。（此處后綴樹指fail指針反向構成的樹）
• f[step][u]表示第step步走到u節點的最優答案
• 需要注意的是如果當前危險節點的模式串長度小于step，答案是不可以更新的，p數組用來判斷這個，相當于表示該狀態有沒有到達過。第一次由于這個WA掉了

---

Code

#include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <cstring> #include <algorithm> using namespace std; queue <int>q; char s[27]; int n,m,sz; int f[1007][307],ch[307][7],val[307],fail[307]; bool p[1007][307]; void insert(char *s,int id){int u=1,n=strlen(s);for (int i=0;i<n;i++){int c=s[i]-'A';if (!ch[u][c]){//memset(ch[sz],0,sizeof(ch[sz]));//val[sz]=0;ch[u][c]=++sz;}u=ch[u][c];}val[u]=1; } void getFail(){int rt=1;fail[rt]=1;for (int i=0;i<3;i++){int u=ch[rt][i];fail[u]=rt;if (u){fail[u]=rt; q.push(u);}else ch[rt][i]=rt;}while (!q.empty()){int u=q.front(); q.pop();for (int i=0;i<3;i++){int v=ch[u][i];if (v){fail[v]=ch[fail[u]][i]; q.push(v);}else ch[u][i]=ch[fail[u]][i];}if (val[fail[u]]) val[u]+=val[fail[u]];} } int main(){scanf("%d%d",&n,&m);sz=1;for (int i=1;i<=n;i++){scanf("%s",s);insert(s,i);}getFail();//printf("sz=%d\n",sz);p[0][1]=1;for (int step=0;step<m;step++)for (int u=1;u<=sz;u++)if (p[step][u])for (int v=0;v<3;v++){int i=ch[u][v];p[step+1][i]=p[step][u];f[step+1][i]=max(f[step+1][i],f[step][u]+val[i]);}//for (int i=1;i<=sz;i++) printf("%d ",val[i]); printf("\n");int ans=0;/*for (int i=0;i<=7;i++)for (int j=1;j<=sz;j++)printf("f[%d][%d]=%d\n",i,j,f[i][j]);*/for (int i=1;i<=sz;i++) ans=max(ans,f[m][i]);printf("%d",ans);return 0; } //SP10502 //Luogu 3041

總結

以上是生活随笔為你收集整理的[USACO12JAN][SPOJ10502][Luogu3041]Video Game Combos的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。