很好的题(又复习了一波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;
}

最新文章

  1. 2-1 Linux 操作系统及常用命令
  2. [LeetCode] Power of Three 判断3的次方数
  3. PHP mysql基础操作
  4. ping: sendto: Network is unreachable
  5. 数论 --- 费马小定理 + 快速幂 HDU 4704 Sum
  6. 给setTimeout和setIntreval函数添加回调参数
  7. VMware Workstation 12 Pro虚拟机下载(含序列号)
  8. cocos2d-x 2.2 资源更新AssetsManager例子代码
  9. VBS基础篇 - 条件语句
  10. python面对对象编程-------5:获取属性的四种办法:@property, __setattr__(__getattr__) ,descriptor
  11. php面试题汇总一(基础篇附答案)
  12. 纯HTML5APP与原生APP的差距在哪?
  13. 关于MVC框架中的Model的理解
  14. PAT 乙级 1070 结绳(25) C++版
  15. HTTP状态代码列表
  16. Sublime Text 使用介绍/全套快捷键及插件推荐
  17. Java List/Set/Map
  18. 2018.8.14-C#复习笔记总
  19. C#aspx页面前台使用&lt;%=%&gt;无法取到后台的值
  20. 【LOJ】#2024. 「JLOI / SHOI2016」侦查守卫

热门文章

  1. jsp-application应用
  2. MySQL基础管理
  3. jq页面换肤效果
  4. Day9, 进程、线程、协程篇
  5. Python3入门机器学习经典算法与应用✍✍✍
  6. C++之变量
  7. maven javaProject打包发布成服务
  8. amaze UI(mark)
  9. Yii2 在php 7.2环境下运行,提示 Cannot use ‘Object’ as class name
  10. leetcode-157周赛-5214-最长定差子序列