当前位置：首页 > news >正文

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

news 2026/5/2 18:33:21

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：6026. 最长公共子上升序列 - 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_j=A_{i_j}Sj=Aij，且对于所有的1 ≤ j < N 1\le j\lt N1≤j<N，均有S j < S j + 1 S_j\lt S_{j+1}Sj<Sj+1。

【输入】

输入共四行，每两行描述一个给定序列，对于每个序列：第一行包含其长度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-一维#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineN505intdp[N][N];// dp[i][j]: x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列的长度intx[N],y[N];// 两个输入序列vector<int>seq[N];// seq[j]: 当i为某确定值时，x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列intmain(){intxn,yn;// 两个序列的长度cin>>xn;// 输入x序列长度// 输入x序列for(inti=1;i<=xn;++i){cin>>x[i];}cin>>yn;// 输入y序列长度// 输入y序列for(inti=1;i<=yn;++i){cin>>y[i];}// 动态规划计算最长公共上升子序列for(inti=1;i<=xn;++i)// 遍历x序列{for(intj=1;j<=yn;++j)// 遍历y序列{if(x[i]==y[j])// 如果当前元素相同{dp[i][j]=1;// 初始化为1seq[j]=vector<int>();// 清空当前序列// 查找可以接在前面的最长公共上升子序列for(intk=1;k<j;++k){if(y[k]<y[j]&&dp[i-1][k]+1>dp[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];// 继承之前的结果}}}// 找到最长的公共上升子序列intmxj=1;// 记录最长子序列在y中的结束位置for(intj=1;j<=yn;j++){if(dp[xn][j]>dp[xn][mxj]){mxj=j;// 更新最大值位置}}// 输出最长公共上升子序列的长度cout<<dp[xn][mxj]<<endl;// 输出最长公共上升子序列的具体元素for(inti=0;i<seq[mxj].size();++i){cout<<seq[mxj][i]<<' ';}return0;// 程序正常结束}