acwing-最长上升公共子序列(动态规划)[通俗易懂]

acwing-最长上升公共子序列(动态规划)[通俗易懂]原题连接熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。小沐沐说,对于两个数列 A 和 B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列,而所有的公共上升子序列中最长的就是最长公共上升子序列了。奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子序列。不过,只要告诉奶牛它的长度就可以了。数列 A 和 B 的长度均不超过 3000。输入格式

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题连接
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。

小沐沐说,对于两个数列 A 和 B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列,而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过,只要告诉奶牛它的长度就可以了。

数列 A 和 B 的长度均不超过 3000。

输入格式
第一行包含一个整数 N,表示数列 A,B 的长度。

第二行包含 N 个整数,表示数列 A。

第三行包含 N 个整数,表示数列 B。

输出格式
输出一个整数,表示最长公共上升子序列的长度。

数据范围
1≤N≤3000,序列中的数字均不超过 231−1。

输入样例:

4
2 2 1 3
2 1 2 3

输出样例:

2

题解
f[i][j]第一个字符串前i个字母和第二个字符串前j个字符,并且第二个字符串以j结尾的最长公共上升字串最大值。
当a[i] != b[j]的时候f[i][j] = f[i-1][j]
当a[i] == b[j]的时候f[i][j] = max(f[i – 1][k],f[i][j]) 当(b[k] < b[j]的时候)其中(1 <= k <= j)

#include<bits/stdc++.h>
#include<cmath>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 1e1 + 10;
const int M = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 4e8;
int n,res = INF;
int a[N],b[N],f[N][N];
int main(){ 
   
    cin>>n;
    for(int i = 1;i <= n;i ++)cin>>a[i];
    for(int i = 1;i <= n;i ++)cin>>b[i];
    int res = 0;
    for(int i = 1;i <= n;i ++){ 
   
        for(int j = 1;j <= n;j ++){ 
   
            if(a[i] != b[j])f[i][j] = f[i - 1][j];
            else{ 
   
                for(int k = 1;k < j;k ++)
                    if(b[j] > b[k])
                        f[i][j] = max(f[i][j],f[i - 1][k]);
                f[i][j] += 1;
            }
            res = max(res,f[i][j]);
        }
    }
    cout<<res<<endl;
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168757.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 粒子群算法的matlab实现(一)[通俗易懂]

    粒子群算法的matlab实现(一)[通俗易懂]粒子群算法(ParticleSwarmOptimization,PSO)是20世纪90年代兴起的一门学科,因其概念简明、实现方便、收敛速度快而为人所知。粒子群算法的基本思想是模拟鸟群随机搜寻食物的捕食行为,鸟群通过自身经验和种群之间的交流调整自己的搜寻路径,从而找到食物最多的地点。其中每只鸟的位置/路径则为自变量组合,每次到达的地点的食物密度即函数值。每次搜寻都会根据自身经验(自身历史搜寻的最

  • idea全局搜索快捷键总结

    一、Ctrl+F或者Ctrl+Shift+R按照文本的内容查找1、相当于eclipse的ctrl+H,Ctrl+F是在本页查找2、相当于eclipse的ctrl+H,Ctrl+Shift+R是全局查找二、Ctrl+Shift+N按文件名搜索文件同搜索类类似,只不过可以匹配所有类型的文件了三、Ctrl+H查看类的继承关系四、Alt+F7查找类或方法在哪被使用五、Sh…

  • Python sorted 函数

    Python sorted 函数Pythonsorted函数sorted可以对所有可迭代的对象进行排序操作,sorted方法返回的是一个新的list,而不是在原来的基础上进行的操作。从新排序列表。sorted语法:

  • PySpark-prophet预测

    PySpark-prophet预测简介Prophet是facebook开源时间序列预测工具,使用时间序列分解与机器学习拟合的方法进行建模预测。关于prophet模型优点我不打算说,网络上的文章非常多,各种可视化,和参数的解释与demo演示。但是在正在用到工业上大规模的可供学习的中文材料并不多。本文打算使用pyspark进行多序列预测建模,会给出一个比较详细的脚本,供交流学习,重点在于使用hive数据/分布式,以及中间数据预处理,以及pandas_udf对多条序列进行循环执行。背景说明,在十万级别的sku序列上使用prophet预测每

  • python数组-1成员_python[1,2,3]*3

    python数组-1成员_python[1,2,3]*3使用python版本3.7首先先了解下python3.7中的下标,python下标有两套,一套是正的,一套是负的a=’python’中的python的下标可以如下组python正下标012345负下标-6-5-4-3-2-1对应位置的正下标-负下标=len(a)使用正下标时,下标i………………………

  • hadoop hdfs命令 脚本源码_hadoop启动hdfs命令

    hadoop hdfs命令 脚本源码_hadoop启动hdfs命令hadoop集群搭建好之后,通过HDFS命令操作HDFS分布式文件系统,HDFS命令与linux命令类似所有命令有/bin/hadoop脚本引发,可以使用命令查看帮助文档hadoopfs-help使用HDFS命令之前,必须启动hadoop集群,且命令执行在master节点上

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号