[Luogu3041][USACO12JAN]视频游戏的连击Video Game Combos
2024-10-11 06:44:01
sol
设\(f_{i,j}\)表示填了前\(i\)个字母,在\(AC\)自动机上跑到了节点\(j\)的最大得分。因为匹配需要暴跳\(fail\)所以预先把\(fail\)指针上面的匹配数传下来,这样就只要计算当前节点的贡献就可以了。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1005;
int n,k,tot,ch[3][N],fail[N],cnt[N],dp[N][N],ans;
char s[N];
queue<int>Q;
void Insert()
{
scanf("%s",s);int l=strlen(s);
int x=0;
for (int i=0;i<l;i++)
{
if (!ch[s[i]-'A'][x]) ch[s[i]-'A'][x]=++tot;
x=ch[s[i]-'A'][x];
}
cnt[x]++;
}
void Get_Fail()
{
for (int i=0;i<3;i++) if (ch[i][0]) Q.push(ch[i][0]);
while (!Q.empty())
{
int u=Q.front();Q.pop();
for (int i=0;i<3;i++)
if (ch[i][u]) fail[ch[i][u]]=ch[i][fail[u]],Q.push(ch[i][u]);
else ch[i][u]=ch[i][fail[u]];
cnt[u]+=cnt[fail[u]];
}
}
void DP()
{
memset(dp,-127,sizeof(dp));dp[0][0]=0;
for (int i=1;i<=k;i++)
for (int j=0;j<=tot;j++)
for (int l=0;l<3;l++)
dp[i][ch[l][j]]=max(dp[i][ch[l][j]],dp[i-1][j]+cnt[ch[l][j]]);
}
int main()
{
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++) Insert();
Get_Fail();
DP();
ans=dp[k][0];
for (int i=1;i<=tot;i++) ans=max(ans,dp[k][i]);
printf("%d\n",ans);
return 0;
}
最新文章
- mac下配置Qt for Android+iOS
- C语言学习001:让程序跑起来
- POJ 2826 An Easy Problem?! --计算几何,叉积
- mysql in 排序
- 在CSV文件中增加一列属性值
- The tag &#39;ChartPlotter&#39; does not exist in XML namespace
- html5的一些表单属性
- (原创)如何在spannableString中使用自定义字体
- UIWebView和UIActivityIndicatorView的结合使用
- MVC Model 数据注解与验证
- (三)一个工作任务引起的乱战——udp通信
- Shared_from_this 几个值得注意的地方
- poj2752 Seek the Name, Seek the Fame(next数组的运用)
- js实现最短时间走完不同速度的路程
- BZOJ 1485: [HNOI2009]有趣的数列 [Catalan数 质因子分解]
- $(";";).append无反应
- [20181124]关于降序索引问题3.txt
- java的第一次博客
- 【附2】hystrix详述(2)- 配置
- DNN例子