洛谷 P3041 视频游戏的连击Video Game Combos(AC自动机+拓扑排序+数位DP)

洛谷 P3041 视频游戏的连击Video Game Combos

难度一般，不过这个数位DP其实应该叫做记忆化搜索

题意：玩游戏时可以通过按键组合打出combo技能；然后是已知N个combo的按键方式，然后求K次按键最多可以放出的combo技能（combo技能之间可以重叠）。

思路：

在AC自动机上如果一个点表示一个字符串以及它的后缀，则一个点可以对应多个combo技能（这是关键点）

可以先用拓扑排序处理出每个点对应了多少个combo技能，处理时要用fail的反向边即refail计算入度(这里应该不用这么麻烦，build的时候就可以直接加上去了)

然后就是数位DP啦，这题没啥坑点，思路简洁

题目描述

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.

输入输出样例

输入
3 7
ABA
CB
ABACB
输出
4
说明/提示

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

//#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) using namespace std; typedef long long ll; typedef pair<int,int> pr; inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}const int maxn = 4e2+10; const int mod = 1e4+7; const double eps = 1e-9;char s[maxn]; int N, K; int trie[maxn][26], fail[maxn], cnt; vector<int> refail[maxn]; int in[maxn], num[maxn]; int dp[1010][maxn];void insert() {int len=strlen(s), p=0;for(int i=0; i<len; ++i) {int k=s[i]-'A';if(!trie[p][k]) trie[p][k]=++cnt;p=trie[p][k];}num[p]++; }void build() {queue<int> q;for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);while(q.size()) {int now=q.front(); q.pop();for(int i=0; i<26; ++i) {if(trie[now][i]) {fail[trie[now][i]]=trie[fail[now]][i];refail[trie[fail[now]][i]].pb(trie[now][i]);in[trie[now][i]]++;q.push(trie[now][i]);}else trie[now][i]=trie[fail[now]][i];}} }void Toposort() {queue<int> q;for(int i=0; i<=cnt; ++i) if(!in[i]) q.push(i);while(q.size()) {int now=q.front(); q.pop();for(int i=0; i<refail[now].size(); ++i) {int v=refail[now][i];num[v]+=num[now];if(--in[v]==0) q.push(v);}} }int dfs(int pos, int now) {if(pos>K) return 0;if(~dp[pos][now]) return dp[pos][now];int ans=0;for(int i=0; i<26; ++i)ans=max(ans,num[trie[now][i]]+dfs(pos+1,trie[now][i]));return dp[pos][now]=ans; }int main() {//ios::sync_with_stdio(false);N=read(), K=read();for(int i=0; i<N; ++i) scanf("%s", s), insert();build();Toposort();memset(dp,-1,sizeof(dp));printf("%d\n", dfs(1,0)); }

总结

以上是生活随笔为你收集整理的洛谷 P3041 视频游戏的连击Video Game Combos(AC自动机+拓扑排序+数位DP)的全部内容，希望文章能够帮你解决所遇到的问题。

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