bzoj3304[Shoi2005]带限制的最长公共子序列 DP
2024-08-31 06:22:21
题意:给出三个序列,求出前两个的公共子序列,且包含第三个序列,要求长度最长。
这道题目怎么做呢,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;
}
最新文章
- Python黑帽编程 3.4 跨越VLAN
- 完整java开发中JDBC连接数据库代码和步骤
- Ninject之旅之十一:Ninject动态工厂(附程序下载)
- Js~动态判断PC和手机浏览器
- 目标检测的图像特征提取之(一)HOG特征(转载)
- 在同步中调用异步方法[.net 4.5]
- yii2 源码分析 object类分析 (一)
- Lecture5_1&;5_2.随机变量的数字特征(数学期望、方差、协方差)
- 能递归检查DataAnnotations的验证函数
- IDEA创建javaSE项目
- linux 远程连接ssh提示IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY解决
- Python&#160;基于Python实现批量创建目录
- 快速简化Android截屏工作
- Java8获取当前时间、新的时间日期类如Java8的LocalDate与Date相互转换、ZonedDateTime等常用操作包含多个使用示例、Java8时区ZoneId的使用方法、Java8时间字符串解析成类
- Flask 邮件发送
- springmvc处理日期格式
- azure 最佳实践 -- 保持冗余
- 今天在Qt子界面中的Button,转到槽转不过去,报错Qt The class containing &#39;Ui::MainWindow&#39; could not be found in...
- iOS 时间转换
- 二维字符数组利用gets()函数输入
热门文章
- 树莓派 VNC 远程桌面 同一个桌面
- node入门(二)——gulpfile.js初探
- ava的动态代理机制详解
- Vue.js学习笔记--3.表单输入绑定
- (6)《Head First HTML与CSS》学习笔记---结尾、《HTML5权威指南》读书笔记
- NavigationView的使用
- git忽略文件权限的检查
- iOS Programming UISplitViewController
- PowerShell让系统可以执行.ps1文件,开机,关机,在线时间 , Function自定义函数
- jquery 微信端 点击物理返回按钮,弹出提示框