【Luogu3041】视频游戏的连击(AC自动机,动态规划)

时间:2023-01-22 13:40:54

题面链接

题解

首先构建出AC自动机

然后在AC自动机上面跑DP

转移很显然从Trie树的节点跳到他的儿子节点

但是要注意一个问题,

在计算的时候,每一个节点加入后能够

造成的贡献

要加上他的子串的贡献

至于DP:

设f[i][j]表示已经使用了i个字母

当前在Trie树的第j个节点上面能够产生的最大贡献

很显然,转移到他的儿子节点上面,同时统计贡献即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1000000
int N,K;
int tot=0,ans;
char s[20];
int f[1100][400];
struct Node
{
int vis[3];
int p;
int fail;
}t[5000];
void Add(char *s)
{
int l=strlen(s);
int now=0;
for(int i=0;i<l;++i)
{
if(!t[now].vis[s[i]-'A'])
t[now].vis[s[i]-'A']=++tot;
now=t[now].vis[s[i]-'A'];
}
t[now].p++;
}
void Build()
{
queue<int> Q;
for(int i=0;i<3;++i)
if(t[0].vis[i])Q.push(t[0].vis[i]);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=0;i<3;++i)
{
if(t[u].vis[i])
{
t[t[u].vis[i]].fail=t[t[u].fail].vis[i];
Q.push(t[u].vis[i]);
}
else
t[u].vis[i]=t[t[u].fail].vis[i];
}
t[u].p+=t[t[u].fail].p;
}
}
void DP()
{
for(int T=0;T<=K;++T)
for(int i=1;i<=tot;++i)
f[T][i]=-INF;
for(int T=1;T<=K;++T)
for(int i=0;i<=tot;++i)
for(int j=0;j<3;++j)
f[T][t[i].vis[j]]=max(f[T][t[i].vis[j]],f[T-1][i]+t[t[i].vis[j]].p);
for(int i=0;i<=tot;++i)ans=max(ans,f[K][i]);
}
int main()
{
scanf("%d%d",&N,&K);
for(int i=1;i<=N;++i)
{
scanf("%s",s);
Add(s);
}
Build();
DP();
printf("%d\n",ans);
return 0;
}

【Luogu3041】视频游戏的连击(AC自动机,动态规划)的更多相关文章

  1. 视频游戏的连击 &lbrack;USACO12JAN&rsqb;&lpar;AC自动机&plus;动态规划&rpar;

    传送门 默认大家都学过trie与AC自动机. 先求出fail,对于每个节点维护一个sum,sum[u]待表从根到u所形成的字符串能拿到几分.显然sum[u]=sum[fail] + (u是几个字符串的 ...

  2. &lbrack;USACO12JAN&rsqb;视频游戏的连击Video Game Combos&lpar;AC自动机&plus;DP&rpar;

    Description 贝西正在打格斗游戏.游戏里只有三个按键,分别是“A”.“B”和“C”.游戏中有 N 种连击 模式,第 i 种连击模式以字符串 Si 表示,只要贝西的按键中出现了这个字符串,就算 ...

  3. 洛谷P3041 视频游戏的连击Video Game Combos &lbrack;USACO12JAN&rsqb; AC自动机&plus;dp

    正解:AC自动机+dp 解题报告: 传送门! 算是个比较套路的AC自动机+dp趴,,, 显然就普普通通地设状态,普普通通地转移,大概就f[i][j]:长度为i匹配到j 唯一注意的是,要加上所有子串的贡 ...

  4. 【洛谷 P3041】 &lbrack;USACO12JAN&rsqb;视频游戏的连击Video Game Combos(AC自动机,dp)

    题目链接 手写一下AC自动机(我可没说我之前不是手写的) Trie上dp,每个点的贡献加上所有是他后缀的串的贡献,也就是这个点到根的fail链的和. #include <cstdio> # ...

  5. &lbrack;洛谷3041&rsqb;视频游戏的连击Video Game Combos

    题目描述 Bessie is playing a video game! In the game, the three letters 'A', 'B', and 'C' are the only v ...

  6. UVA - 11468 &lpar;AC自动机&plus;动态规划&rpar;

    建立AC自动机,把AC自动机当做一张图,在上面跑L个节点就行了. 参考了刘汝佳的代码,发现可能有一个潜在的Bug--如果模式串中出现了没有指定的字符,AC自动机可能会建立出错. 提供一组关于这个BUG ...

  7. BZOJ1030 &lbrack;JSOI2007&rsqb;文本生成器 AC自动机 动态规划

    欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1030 题意概括 给出n个模式串,问长度为m的串中有多少个至少含有这n个模式串中的任意一个. 注意, ...

  8. 【BZOJ1030】&lbrack;JSOI2007&rsqb;文本生成器 AC自动机&plus;动态规划

    [BZOJ1030][JSOI2007]文本生成器 Description JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文 ...

  9. 【题解】&lbrack;USACO12JAN&rsqb;视频游戏的连击Video Game Combos

    好久没有写博客了,好惭愧啊……虽然这是一道弱题但还是写一下吧. 这道题目的思路应该说是很容易形成:字符串+最大值?自然联想到学过的AC自动机与DP.对于给定的字符串建立出AC自动机,dp状态dp[i] ...

随机推荐

  1. knockoutJS学习笔记09:使用mapping插件

    一.问题引出 通常,我们先定义好html结构或者模板,通过ajax向后台发起请求,后台返回json数据,然后再将json数据渲染到页面上.以博客园个人博客里的个人信息为例子,如图: 1.定义html. ...

  2. jQuery MiniUI Demo

    http://www.miniui.com/demo/#src=datagrid/datagrid.html

  3. WPF &plus; Caliburn&period;Micro &plus;ActionMessage事件绑定

    ActionMessage事件绑定是个人觉的算是CM的精髓了,比如说我在View里面放个button,我们要在他的click事件里面写东西,怎么写.如果是WPF我们直接在CS里面写就可以.但是CM不行 ...

  4. OpenCV检测人脸实例代码

    下面是使用OpenCV通过在硬盘中读入图像来对其进行Haar人脸检测的代码. //包含头文件 #include <opencv2/core/core.hpp> #include &quot ...

  5. openfire数据库中文乱码问题

    1.首先数据库的编码设置为UTF-8 2.项目的编码也要设置为UTF-8 假设数据保存到数据库的时候还有乱码  就要改动openfire配置文件 在openfire主文件夹\conf\openfire ...

  6. Python就业指导

    一年一度的金三银四招聘旺季又要到了,最近有很多同学希望我能给他们一些关于python的就业指导:之前出过一期关于java的就业指导,但是并不是很完善,所以希望这期关于python的就业指导能够很全面很 ...

  7. k-means缺陷

    k均值算法非常简单且使用广泛,但是存在的缺陷有: 1. K值需要预先给定: 属于预先知识,很多情况下K值的估计非常困难. 2. K-Means算法对初始选取的聚类中心点是敏感的: 不同的随机种子点得到 ...

  8. 点击倒计时60S获取验证码

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <script sr ...

  9. C&num; 读写 ini 配置文件

    虽说 XML 文件越发流行,但精简的 ini 配置文件还是经常会用到,在此留个脚印. 当然,文中只是调用系统API,不会报错,如有必要,也可以直接以流形式读取 ini文件并解析. /// <su ...

  10. centos7装NVIDIA显卡驱动

    一.系统及显卡 系统:centos7.5 64位 显卡:gtx 1060 前几天主要是有一个人脸识别的项目测试,需要用到显卡去测试性能,然后装显卡的过程折腾了一下,特此记录. 二.安装过程 1. 下载 ...