题目描述
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。
小沐沐说,对于两个数列 A和B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列,而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过,只要告诉奶牛它的长度就可以了。
数列 A和 B的长度均不超过 3000。
题目大意
有a,b两个数列,现在你要找到a,b数列的最大公共子序列,且该序列是上升的
算法1
$O(n^3)$
这显然是一个emmm……DP题
那么我们不妨设$f _ {ij}$表示
在前$a _ i$的序列中选择数,其中以$b _ j$结尾的最长序列长度
那么我们可以来考虑
当$a _ i$$=$$b _ j$时,那么我们就要去暴力搜索能满足LCIS条件的序列
核心代码
if(a[i]==b[j]){
for(int k=0;k<j;++k)
if(a[i]>b[k]){
f[i][j]=max(f[i][j],f[i-1][k]+1);
}
}
怎么个事儿啊?
我们来看一组数据
4 5 7 4 5 6 7
4 5 3 4 7 3 4
此时我们看到搜索到$i=3$ $j=5$时值均为7
此时我们暴力从头开始找,4<7,符合要求,$f _ {1,1}+1$判断与$f _ {3,5}$大小,若大则更新因为在这里面有比原来更长的序列。以此类推一直往下找。
#include <cstdio>
#include <cctype>
#define maxn 505
inline int read() {
int d=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){d=d*10+ch-48;ch=getchar();}return d;
}
int n, m, a[maxn], b[maxn];
int f[maxn][maxn], pre[maxn][maxn];
int ans, sp;
int st[maxn], tot;
int main() {
n = read(); for(int i = 1; i <= n; ++i) a[i] = read();
m = read(); for(int i = 1; i <= m; ++i) b[i] = read();
a[0] = b[0] = -1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
if(a[i] == b[j]) { // 可以将a[i]加入
for(int k = 0; k < j; ++k)
if(a[i] > b[k]) { // 这里a[i]既为b[j]
f[i][j]=max(f[i][j],f[i-1][k]+1);
}
}
else { // 不能加入a[i]
f[i][j] = f[i-1][j];
}
}
cout<<f[n][m]<<endl;
return 0;
}
好吧说实话这是我从洛谷上面随便找了一个题解放上来的
来自https://www.luogu.com.cn/user/79017
时间复杂度$O(n^3)$
算法2
$O(n^2)$
作为一名初学者,当时看到上一个代码的时候,我就有一种莫名的奇怪——好像k的那个三层循环有点多余
详细的可以去看LYD的书,反正他写的那句话我是没看懂。
但是你可这么理解。
因为在第二层j的循环的时候,i是一个定值,所以b[k]<a[i]一定是个定值
所以我们用一个val来记录他,如果循环到b[j]<a[i],我们就把val更新成val和$f _ {i-1j}$的大者
时间复杂度$O(n^2)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[505],b[505];
int f[505][505];
int main(){
cin>>n;for(int i=1;i<=n;i++) cin>>a[i];
m=n;for(int j=1;j<=m;j++) cin>>b[j];
a[0]=b[0]=-1;
for(int i=1;i<=n;i++){
int val=0;
if(b[0]<a[i]) val=f[i-1][0];
for(int j=1;j<=m;j++){
if(a[i]==b[j]) f[i][j]=val+1;
else f[i][j]=f[i-1][j];
if(a[i]>b[j]) val=max(f[i-1][j],val);
}
}
cout<<f[n][m]<<endl;
return 0;
}
这个是我自己打的了
in the end
非常感谢读者能阅读完这篇题解
本作这是一个新手,在语言表达和latex的使用上不是很好请谅解