DP经典问题—————(LCIS)最长公共上升子序列
2024-09-02 02:24:05
这道题是LIS(最长上升子序列)与LCS(最长公共子序列)问题的综合版本,有关这两个问题可以看一下我的文章:https://www.cnblogs.com/myhnb/p/11305551.html
把这两个问题的解法结合,不难想到以下方法
C++代码
#include<bits/stdc++.h>
using namespace std; const int N=;
int a[N],b[N];
int f[N][N];
int n; int main(){
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++) cin>>b[i]; for(int i=;i<=n;i++){
int maxv=; //前边最多有多少个满足b[j]<a[i]的
for(int j=;j<=n;j++){
f[i][j]=f[i-][j];
if(a[i]==b[j]) f[i][j]=max(f[i][j],maxv+); //更新答案 if(b[j]<a[i]) maxv=max(maxv,f[i][j]);//更新maxv
}
} int res=;
for(int i=;i<=n;i++) res=max(res,f[n][i]); cout<<res<<endl;
}
最新文章
- WeCenter二次开发教程(一):熟悉模板结构
- C#获取IP地址
- enum使用
- 腾讯云ubuntu下mysqli服务的开启
- mysql 导入导出的几个常用参数
- Javascript 基础--JS函数(三)
- jsp页面el表达式不起作用
- 致vi老大 2011.1
- LRU 缓冲池 (不考虑多线程)
- 常用 Linux 命令
- AC自动机(模板)
- DjangoORM一对多&多对多操作
- SQL2008无法连接到.,及sa登录失败的总结
- ado.net 参数传递之 in
- 高德地图 Service 创建服务 USERKEY_PLAT_NOMATCH
- Android系统修改之Notification布局修改(一)
- SDL2.0 vs2017环境配置
- Python学习笔记(三)
- SQLLITE HELPER
- java的输入输出