時空限制 1000ms / 128MB

題目描述

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?

貝西在玩一款游戲，該游戲只有三個技能鍵 “A”“B”“C”可用，但這些鍵可用形成N種(1 <= N<= 20)特定的組合技。第i個組合技用一個長度為1到15的字符串S_i表示。

當貝西輸入的一個字符序列和一個組合技匹配的時候，他將獲得1分。特殊的，他輸入的一個字符序列有可能同時和若干個組合技匹配，比如N=3時，3種組合技分別為"ABA", “CB”, 和"ABACB",若貝西輸入"ABACB"，他將獲得3分。

若貝西輸入恰好K (1 <= K <= 1,000)個字符，他最多能獲得多少分？

輸入格式：

• 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.

輸出格式：

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

---

題目分析

AC自動機的DP永遠都一個套路
$dp[i][j]$表示已完成字符串前$i$位，當前在AC自動機上結點$j$，最多可得多少分
初始化為$dp[0][0]=0$，其余為-INF
$dp[i][ch[j][k]]=max(dp[i][ch[j][k]],dp[i?1][j]+num[ch[j][k]])$
注意一個技能是另一個技能子串時，技能個數要累加到那個最長的字符串上

---

#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<cstring> #include<cstdio> using namespace std; typedef long long lt; typedef double dd;int read() {int f=1,x=0;char ss=getchar();while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}return f*x; }const int maxn=1010; int n,L; int rem[maxn],cnt; int ch[maxn][5],fail[maxn]; int dp[maxn][maxn],ans; char pt[maxn];void ins(char* ss,int len) {int u=0;for(int i=0;i<len;++i){int x=ss[i]-'A';if(!ch[u][x]) ch[u][x]=++cnt;u=ch[u][x];}rem[u]++; }void ACM() {queue<int> q;for(int i=0;i<3;++i)if(ch[0][i]) fail[ch[0][i]]=0,q.push(ch[0][i]);while(!q.empty()){int u=q.front(); q.pop();for(int i=0;i<3;++i){if(!ch[u][i]) ch[u][i]=ch[fail[u]][i];else{fail[ch[u][i]]=ch[fail[u]][i];q.push(ch[u][i]);rem[ch[u][i]]+=rem[fail[ch[u][i]]];}}} }void DP() {memset(dp,128,sizeof(dp)); dp[0][0]=0;for(int i=1;i<=L;++i)for(int j=0;j<=cnt;++j){for(int k=0;k<3;++k)dp[i][ch[j][k]]=max(dp[i][ch[j][k]],dp[i-1][j]+rem[ch[j][k]]);}for(int i=0;i<=cnt;++i)ans=max(ans,dp[L][i]); }int main() {n=read();L=read();for(int i=1;i<=n;++i){scanf("%s",&pt);ins(pt,strlen(pt));}ACM(); DP();printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的P3041 [USACO12JAN]Video Game Combos【AC自动机+DP】的全部內容，希望文章能夠幫你解決所遇到的問題。

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