第九章动态规划-1306：最长公共子上升序列_1306:最长公共子上升序列-程序员宅基地

1306：最长公共子上升序列

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 1808 通过数: 1006
【题目描述】
给定两个整数序列，写一个程序求它们的最长上升公共子序列。

当以下条件满足的时候，我们将长度N的序列S1,S2,…,SN 称为长度为M的序列A1,A2,…,AM的上升子序列：

存在1≤i1<i2<…<iN≤M，使得对所有1≤j≤N，均有Sj=Aij，且对于所有的1≤j<N，均有Sj<Sj+1。

【输入】
每个序列用两行表示，第一行是长度M(1≤M≤500)，第二行是该序列的M个整数Ai(−231≤Ai<231)
【输出】
在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。

【输入样例】
5
1 4 2 5 -12
4
-12 1 2 4
【输出样例】
2
1 4

思路：a[i] ！= b[j]时， d[i][j] = d[i-1][j]; 因为 d[i][j] 是以 b[j] 为结尾的LCIS，如果 d[i][j] > 0 那么就说明 a[1] … a[i] 中必然有一个元素 a[k] 等于 b[j]。因为 a[k] != a[i]，那么 a[i] 对 d[i][j] 没有贡献，于是我们不考虑它照样能得出 d[i][j] 的最优值。所以在 a[i] != b[j] 的情况下必然有 d[i][j] = d[i-1][j]。
状态转移方程：

a[i] != b[j]: d[i][j]=d[i-1][j] ；

a[i] == b[j]: d[i][j]=max(d[i-1][k]) + 1 ；（1<= k <= j-1）

这是一个时间复杂度为O(n^3)的dp.
如何变成O(n^2）,保证到i、j为止的最大长度不可能小于i-1，j的,/只要以一个序列为准记住p就可以,i不变，遍历j，此时要保证j序列值要小才可以是上升序列,if (a[i] > b[j] && mx < dp[i-1][j]),记录dp[i-1][0~j]的最大值,记录此时的j值,if (a[i] == b[j]) ,dp[i][j] = mx+1;p[i][j] = y;ans = max(ans,dp[i][j]);就是最后所求。

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#define N 505
using namespace std;
long long a[N],b[N],k[N];
int dp[N

本文链接：https://blog.csdn.net/zqhf123/article/details/105862530

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios