技术标签： 算法 信息学C++ 一本通 动态规划 数据结构
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文章浏览阅读1.2k次，点赞35次，收藏18次。AutowiredPostConstruct 注释用于在依赖关系注入完成之后需要执行的方法上，以执行任何初始化。此方法必须在将类放入服务之前调用。支持依赖关系注入的所有类都必须支持此注释。即使类没有请求注入任何资源，用 PostConstruct 注释的方法也必须被调用。只有一个方法可以用此注释进行注释。_springboot2.7获取bean
文章浏览阅读2.1k次。理论介绍 节点定义package logistic;public class Instance { public int label; public double[] x; public Instance(){} public Instance(int label,double[] x){ this.label = label; th_logisticregression java
文章浏览阅读981次，点赞21次，收藏18次。本书是获得了很多读者好评的Linux经典畅销书**《Linux从入门到精通》的第2版**。下面我们来进行文件的恢复，执行下文中的lsof命令，在其返回结果中我们可以看到test-recovery.txt (deleted)被删除了，但是其存在一个进程tail使用它，tail进程的进程编号是1535。我们看到文件名为3的文件，就是我们刚刚“误删除”的文件，所以我们使用下面的cp命令把它恢复回去。命令进入该进程的文件目录下，1535是tail进程的进程id，这个文件目录里包含了若干该进程正在打开使用的文件。
文章浏览阅读10w+次，点赞12次，收藏72次。RTMP(Real Time Messaging Protocol)实时消息传输协议是Adobe公司提出得一种媒体流传输协议，其提供了一个双向得通道消息服务，意图在通信端之间传递带有时间信息得视频、音频和数据消息流，其通过对不同类型得消息分配不同得优先级，进而在网传能力限制下确定各种消息得传输次序。_rtmp
文章浏览阅读64次。2017年12月的计算机等级考试将要来临!出国留学网为考生们整理了2017年12月计算机一级MSOffice考试习题，希望能帮到大家，想了解更多计算机等级考试消息，请关注我们，我们会第一时间更新。2017年12月计算机一级MSOffice考试习题(二)一、单选题1). 计算机最主要的工作特点是( )。A.存储程序与自动控制B.高速度与高精度C.可靠性与可用性D.有记忆能力正确答案：A答案解析：计算...
文章浏览阅读356次。在学MYSQL的时候刚刚好看到了这个提权，很久之前用过别人现成的，但是一直时间没去细想， 这次就自己复现学习下。 0x00 UDF 什么是UDF？ UDF (user defined function)，即用户自定义函数。是通过添加新函数，对MySQL的功能进行扩充，就像使..._the provided input file '/usr/share/metasploit-framework/data/exploits/mysql
文章浏览阅读3.1w次，点赞71次，收藏485次。webService一 WebService概述1.1 WebService是什么WebService是一种跨编程语言和跨操作系统平台的远程调用技术。Web service是一个平台独立的，低耦合的，自包含的、基于可编程的web的应用程序，可使用开放的XML（标准通用标记语言下的一个子集）标准...
文章浏览阅读1w次。前言照例给出官网：Retrofit官网其实大家学习的时候，完全可以按照官网Introduction，自己写一个例子来运行。但是百密一疏，官网可能忘记添加了一句非常重要的话，导致你可能出现如下错误：Could not locate ResponseBody converter错误信息：Caused by: java.lang.IllegalArgumentException: Could not l_已添加addconverterfactory 但是 could not locate responsebody converter
文章浏览阅读1k次。一套键鼠控制Windows+Linux——Synergy在Windows10和Ubuntu18.04共控的实践Synergy简介准备工作（重要）Windows服务端配置Ubuntu客户端配置配置开机启动Synergy简介Synergy能够通过IP地址实现一套键鼠对多系统、多终端进行控制，免去了对不同终端操作时频繁切换键鼠的麻烦，可跨平台使用，拥有Linux、MacOS、Windows多个版本。Synergy应用分服务端和客户端，服务端即主控端，Synergy会共享连接服务端的键鼠给客户端终端使用。本文_linux 18.04 synergy
文章浏览阅读374次。写demo的时候遇到了很多问题，记录一下。安装nacos1.4.0配置mysql数据库，新建nacos_config数据库，并根据初始化脚本新建表，使配置从数据库读取，可单机模式启动也可以集群模式启动，启动时 ./start.sh -m standaloneapplication.properties 主要是db部分配置## Copyright 1999-2018 Alibaba Group Holding Ltd.## Licensed under the Apache License,_seata1.4.0 +nacos 集成
文章浏览阅读833次。iperf使用方法详解 iperf3是一款带宽测试工具，它支持调节各种参数，比如通信协议，数据包个数，发送持续时间，测试完会报告网络带宽，丢包率和其他参数。 安装 sudo apt-get install iperf3 iPerf3常用的参数： -c ：指定客户端模式。例如：iperf3 -c 192.168.1.100。这将使用客户端模式连接到IP地址为192.16..._iperf客户端指定ip地址
文章浏览阅读7.4k次。 写这个函数目的不是为了和C/C++库中的函数在性能和安全性上一比高低，只是为了给那些喜欢探讨函数内部实现的网友，提供一种从浮点性到字符串转换的一种途径。 浮点数是有精度限制的，所以即使我们在使用C/C++中的sprintf或者cout 限制，当然这个精度限制是可以修改的。比方在C++中，我们可以cout.precision(10),不过这样设置的整个输出字符长度为10，而不是特定的小数点后1_c++浮点数 转 字符串 精度损失最小