这道题是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;
}

最新文章

  1. WeCenter二次开发教程(一):熟悉模板结构
  2. C#获取IP地址
  3. enum使用
  4. 腾讯云ubuntu下mysqli服务的开启
  5. mysql 导入导出的几个常用参数
  6. Javascript 基础--JS函数(三)
  7. jsp页面el表达式不起作用
  8. 致vi老大 2011.1
  9. LRU 缓冲池 (不考虑多线程)
  10. 常用 Linux 命令
  11. AC自动机(模板)
  12. DjangoORM一对多&多对多操作
  13. SQL2008无法连接到.,及sa登录失败的总结
  14. ado.net 参数传递之 in
  15. 高德地图 Service 创建服务 USERKEY_PLAT_NOMATCH
  16. Android系统修改之Notification布局修改(一)
  17. SDL2.0 vs2017环境配置
  18. Python学习笔记(三)
  19. SQLLITE HELPER
  20. java的输入输出

热门文章

  1. C# Transaction 事务处理 -依赖事务
  2. Qt disconnect函数
  3. 题解 [CF961G] Partitions
  4. socket、tcp、udp、http 的认识
  5. find(expr|obj|ele)搜索所有与指定表达式匹配的元素。
  6. 通俗理解数字签名,ssl数字证书和https
  7. ueditor上粘贴从word中copy的图片和文字
  8. jQuery系列(三):jQuery动画效果
  9. GC 老年代 新生代
  10. [笔记]C++拷贝构造和移动构造