题意:给出三个序列,求出前两个的公共子序列,且包含第三个序列,要求长度最长。

这道题目怎么做呢,f[i][j]表示a串1-i,b串1-j的最长,g[i][j]表示a串i-n,b串j-m最长,

那么只需要判断中间有没有包好c串就OK了,这样都是O(n^2)的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define N 3008
#define mx 1e9
using namespace std;
int sc()
{
int i=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
return i*f;
}
int fa[N],fb[N];
int f[N][N],g[N][N];
int a[N],b[N],c[N];
int La,Lb,Lc,ans;
int main()
{
La=sc();for(int i=1;i<=La;i++)a[i]=sc();
Lb=sc();for(int i=1;i<=Lb;i++)b[i]=sc();
Lc=sc();for(int i=1;i<=Lc;i++)c[i]=sc();
for(int i=1;i<=La;i++)
for(int j=1;j<=Lb;j++)
if(a[i]==b[j])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max(f[i][j-1],f[i-1][j]);
if(!Lc)
{
printf("%d\n",f[La][Lb]);
return 0;
}
for(int i=La;i>=1;i--)
for(int j=Lb;j>=1;j--)
if(a[i]==b[j])
g[i][j]=g[i+1][j+1]+1;
else
g[i][j]=max(g[i][j+1],g[i+1][j]);
for(int i=1;i<=La;i++)
if(i>1&&a[i-1]!=c[1])fa[i]=fa[i-1];
else for(int j=1,k=i;k<=La;k++)
{
if(a[k]==c[j])j++;
if(j>Lc){fa[i]=k;break;}
}
for(int i=1;i<=Lb;i++)
if(i>1&&b[i-1]!=c[1])fb[i]=fb[i-1];
else for(int j=1,k=i;k<=Lb;k++)
{
if(b[k]==c[j])j++;
if(j>Lc){fb[i]=k;break;}
}
for(int i=1;i<=La;i++)
if(fa[i])
for(int j=1;j<=Lb;j++)
if(fb[j])
ans=max(ans,f[i-1][j-1]+g[fa[i]+1][fb[j]+1]);
ans?cout<<ans+Lc:cout<<-1;
}

  

最新文章

  1. Python黑帽编程 3.4 跨越VLAN
  2. 完整java开发中JDBC连接数据库代码和步骤
  3. Ninject之旅之十一:Ninject动态工厂(附程序下载)
  4. Js~动态判断PC和手机浏览器
  5. 目标检测的图像特征提取之(一)HOG特征(转载)
  6. 在同步中调用异步方法[.net 4.5]
  7. yii2 源码分析 object类分析 (一)
  8. Lecture5_1&amp;5_2.随机变量的数字特征(数学期望、方差、协方差)
  9. 能递归检查DataAnnotations的验证函数
  10. IDEA创建javaSE项目
  11. linux 远程连接ssh提示IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY解决
  12. Python&#160;基于Python实现批量创建目录
  13. 快速简化Android截屏工作
  14. Java8获取当前时间、新的时间日期类如Java8的LocalDate与Date相互转换、ZonedDateTime等常用操作包含多个使用示例、Java8时区ZoneId的使用方法、Java8时间字符串解析成类
  15. Flask 邮件发送
  16. springmvc处理日期格式
  17. azure 最佳实践 -- 保持冗余
  18. 今天在Qt子界面中的Button,转到槽转不过去,报错Qt The class containing &#39;Ui::MainWindow&#39; could not be found in...
  19. iOS 时间转换
  20. 二维字符数组利用gets()函数输入

热门文章

  1. 树莓派 VNC 远程桌面 同一个桌面
  2. node入门(二)——gulpfile.js初探
  3. ava的动态代理机制详解
  4. Vue.js学习笔记--3.表单输入绑定
  5. (6)《Head First HTML与CSS》学习笔记---结尾、《HTML5权威指南》读书笔记
  6. NavigationView的使用
  7. git忽略文件权限的检查
  8. iOS Programming UISplitViewController
  9. PowerShell让系统可以执行.ps1文件,开机,关机,在线时间 , Function自定义函数
  10. jquery 微信端 点击物理返回按钮,弹出提示框