题解：AcWing 6026 最长公共子上升序列

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6026. 最长公共子上升序列 - AcWing题库【题目描述】给定两个整数序列写一个程序求它们的最长上升公共子序列。当以下条件满足的时候我们将长度N NN的序列S 1 , S 2 , … , S N S_1,S_2,\dots,S_NS1​,S2​,…,SN​称为长度为M MM的序列A 1 , A 2 , … , A M A_1,A_2,\dots,A_MA1​,A2​,…,AM​的上升子序列存在1 ≤ i 1 i 2 ⋯ i N ≤ M 1\le i_1\lt i_2\lt \dots \lt i_N\le M1≤i1​i2​⋯iN​≤M使得对所有1 ≤ j ≤ N 1\le j\le N1≤j≤N均有S j A i j S_jA_{i_j}Sj​Aij​​且对于所有的1 ≤ j N 1\le j\lt N1≤jN均有S j S j 1 S_j\lt S_{j1}Sj​Sj1​。【输入】输入共四行每两行描述一个给定序列对于每个序列第一行包含其长度M MM第二行包含其序列元素A 1 , A 2 , … , A M A_1,A_2,\dots,A_MA1​,A2​,…,AM​。两个序列的长度不一定相同。【输出】在第一行输出两个序列的最长上升公共子序列的长度L LL。在第二行输出该子序列。如果有不止一个符合条件的子序列则输出任何一个即可。【输入样例】5 1 4 2 5 -12 4 -12 1 2 4【输出样例】2 1 4【算法标签】#线性DP-一维#【代码详解】#includebits/stdc.husingnamespacestd;#defineN505intdp[N][N];// dp[i][j]: x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列的长度intx[N],y[N];// 两个输入序列vectorintseq[N];// seq[j]: 当i为某确定值时x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列intmain(){intxn,yn;// 两个序列的长度cinxn;// 输入x序列长度// 输入x序列for(inti1;ixn;i){cinx[i];}cinyn;// 输入y序列长度// 输入y序列for(inti1;iyn;i){ciny[i];}// 动态规划计算最长公共上升子序列for(inti1;ixn;i)// 遍历x序列{for(intj1;jyn;j)// 遍历y序列{if(x[i]y[j])// 如果当前元素相同{dp[i][j]1;// 初始化为1seq[j]vectorint();// 清空当前序列// 查找可以接在前面的最长公共上升子序列for(intk1;kj;k){if(y[k]y[j]dp[i-1][k]1dp[i][j])// 上升且可以延长{dp[i][j]dp[i-1][k]1;// 更新长度seq[j]seq[k];// 继承序列}}seq[j].push_back(y[j]);// 添加当前元素}else// 如果当前元素不同{dp[i][j]dp[i-1][j];// 继承之前的结果}}}// 找到最长的公共上升子序列intmxj1;// 记录最长子序列在y中的结束位置for(intj1;jyn;j){if(dp[xn][j]dp[xn][mxj]){mxjj;// 更新最大值位置}}// 输出最长公共上升子序列的长度coutdp[xn][mxj]endl;// 输出最长公共上升子序列的具体元素for(inti0;iseq[mxj].size();i){coutseq[mxj][i] ;}return0;// 程序正常结束}【运行结果】5 1 4 2 5 -12 4 -12 1 2 4 2 1 4