字符串+dp——cf1163D好题
2024-09-18 07:45:40
很好的题(又复习了一波kmp)
/*
dp[i,j,k]:到s1的第i位,匹配s2到j,s3到k的最优解
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 2005
int len1,len2,len3,dp[maxn][][],f2[],f3[];
char s1[maxn],s2[],s3[]; void kmp(char *s,int *f){
int len=strlen(s);
int i,j;
j=f[]=-,i=;
while(i<len){
while(j!=- && s[i]!=s[j])j=f[j];
f[++i]=++j;
}
} int main(){
scanf("%s%s%s",s1+,s2,s3);
len1=strlen(s1+);len2=strlen(s2);len3=strlen(s3);
for(int i=;i<=;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
dp[i][j][k]=-0x3f3f3f3f;
int ans=-0x3f3f3f3f;
dp[][][]=;
kmp(s2,f2),kmp(s3,f3);
for(int i=;i<=len1;i++)
for(int j=;j<=len2;j++)//这里一定要等于
for(int k=;k<=len3;k++)//从[i-1,j,k]状态推导到当前状态
if(dp[i-][j][k]!=-0x3f3f3f3f){
char L='a',R='z';
if(s1[i]!='*')L=R=s1[i];
for(char ch=L;ch<=R;ch++){//枚举第i位选的是字符ch
//找选了ch在s2,s3的匹配位置
int p2=j,p3=k,tmp=;
while(p2!=- && s2[p2]!=ch)
p2=f2[p2];
p2++;
while(p3!=- && s3[p3]!=ch)
p3=f3[p3];
p3++; if(p2==len2)tmp++;
if(p3==len3)tmp--;
dp[i][p2][p3]=max(dp[i][p2][p3],dp[i-][j][k]+tmp);
if(i==len1)
ans=max(ans,dp[i][p2][p3]);
}
}
cout<<ans<<endl;
}
最新文章
- 2-1 Linux 操作系统及常用命令
- [LeetCode] Power of Three 判断3的次方数
- PHP mysql基础操作
- ping: sendto: Network is unreachable
- 数论 --- 费马小定理 + 快速幂 HDU 4704 Sum
- 给setTimeout和setIntreval函数添加回调参数
- VMware Workstation 12 Pro虚拟机下载(含序列号)
- cocos2d-x 2.2 资源更新AssetsManager例子代码
- VBS基础篇 - 条件语句
- python面对对象编程-------5:获取属性的四种办法:@property, __setattr__(__getattr__) ,descriptor
- php面试题汇总一(基础篇附答案)
- 纯HTML5APP与原生APP的差距在哪?
- 关于MVC框架中的Model的理解
- PAT 乙级 1070 结绳(25) C++版
- HTTP状态代码列表
- Sublime Text 使用介绍/全套快捷键及插件推荐
- Java List/Set/Map
- 2018.8.14-C#复习笔记总
- C#aspx页面前台使用<;%=%>;无法取到后台的值
- 【LOJ】#2024. 「JLOI / SHOI2016」侦查守卫