luogu P3041 [USACO12JAN]视频游戏的连击Video Game Combos

P3041 [USACO12JAN]视频游戏的连击Video Game Combos

题目大意：

给出n个字符串st[1…n]，求一个长度为K的字符串，每匹配到st中的字符串就+1分，问最多能加几分

题解

做法十分套路，
先把AC自动机建出来，在建的时候继承一下nxt的信息
然后就是很简单的DP了

code：

// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 305 #define C 3 using namespace std; int ch[N][C], nxt[N], size[N], n, dp[1005][N], tot, K; string st; void insert(){ //插♂入int p = 0, len = st.length();for(int i = 0;i < len; i ++){if(!ch[p][st[i] - 'A']) ch[p][st[i] - 'A'] = ++ tot;p = ch[p][st[i] - 'A'];}size[p] ++;//记一下大小 } queue<int> q; void build(){//日常建树for(int i = 0; i < C; i ++) if(ch[0][i]) q.push(ch[0][i]);while(q.size()){int u = q.front(); q.pop();size[u] += size[nxt[u]];//继承一下nxt的信息，这样匹配一下就行了，不用每次暴力网上跳for(int i = 0; i < C; i ++){if(ch[u][i]){nxt[ch[u][i]] = ch[nxt[u]][i];q.push(ch[u][i]);}else ch[u][i] = ch[nxt[u]][i];}} } int main(){cin >> n >> K;for(int i = 1; i <= n; i ++) cin >> st, insert();build();//DP，dp[i][j] 表示现在是第i位，在AC自动机上的第j个节点，最大的值是多少dp[0][0] = 1;//这是个小技巧，先把初值设为1，最后答案再减1，这样就不用吧其他的全都设为-INF了for(int i = 0; i < K; i ++) for(int j = 0; j <= tot; j ++){if(!dp[i][j]) continue;for(int k = 0; k < C; k ++){int v = ch[j][k];dp[i + 1][v] = max(dp[i + 1][v], dp[i][j] + size[v]);//简单的转移}}int ans = 0;for(int i = 0; i <= tot; i ++) ans = max(ans, dp[K][i]);//找最大cout << ans - 1;//记得减回一return 0; }

坑点：

貌似没有，就-INF吧

总结

以上是生活随笔为你收集整理的luogu P3041 [USACO12JAN]视频游戏的连击Video Game Combos的全部内容，希望文章能够帮你解决所遇到的问题。

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