A39795. 最长公共上升子序列
填空题
困难
知识点
题目描述
最长公共上升子序列
题目描述
给定两个整数序列，写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候，我们将长度NN的序列S1,S2,...,SNS1,S2,...,SN 称为长度为MM的序列A1,A2,...,AMA1,A2,...,AM的上升子序列：
存在1≤i1<i2<...<iN≤M1≤i1<i2<...<iN≤M，使得对所有1≤j≤N1≤j≤N，均有Sj=AijSj=Aij，且对于所有的1≤j<N1≤j<N，均有Sj<Sj+1Sj<Sj+1。
输入
每个序列用两行表示，第一行是长度M(1≤M≤500)M(1≤M≤500)，第二行是该序列的M个整数Ai(−231<=Ai<231)Ai(−231<=Ai<231)
输出
在第一行，输出两个序列的最长上升公共子序列的长度LL。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。
输入样例
5
1 4 2 5 -12
4
-12 1 2 4
输出样例
2
1 4
参考答案
#include<bits/stdc++.h>
using namespace std;
int n,m,a[501],b[501],d[501][501],pre[501];
void print(int x){
if (x==0) return;
print(pre[x]);
printf("%d ",b[x]);
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",a+i);
scanf("%d",&m);
for (int i=1;i<=m;++i) scanf("%d",b+i);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j){
d[i][j]=d[i-1][j];
if (a[i]==b[j]){
int maxn=0,ind=0;
for (int k=1;k<=j-1;++k)
if (d[i-1][k]>maxn && b[k]<b[j]){
maxn=d[i-1][k];
ind=k;
}
d[i][j]=maxn+1;
pre[j]=ind;
}
}
int ans=0,ind=0;
for (int j=1;j<=m;++j)
if (ans<d[n][j]){
ans=d[n][j];
ind=j;
}
cout<<ans<<endl;
print(ind);
cout<<endl;
return 0;
}
上一题
下一题