#动态规划，线性动态规划#codevs 2185 CH 5101 LCIS 最长公共上升子序列

本文主要是介绍#动态规划，线性动态规划#codevs 2185 CH 5101 LCIS 最长公共上升子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求两个序列的最长公共上升子序列

分析

首先，优化的方法

for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)if (a[i]==b[j])for (int k=0;k<j;k++)if (b[k]<a[i])f[i][j]=max(f[i][j],f[i-1][k]+1);

但是 $O(n^3)$ 的算法对于 $n\leq 3000$ 的数据是无法承受的，所以应该怎么优化呢?
冗余的地方就是不断地 $k$ 循环，所以可以考虑 $k$ ， $i$ 是可以定下来的，所以 $b [k] < a [i]$ 是固定的，当 $j$ 增加时，k也会因此增加，所以只要判断 $b [j] < a [i]$ ，已经可以满足的k就不会被遗漏
放上滚动的 $O(n^2)$ 算法

for (int i=1;i<=n;i++){int maxx=0;//表示包含i的上升子序列的最长长度for (int j=1;j<=n;j++)if (b[j]<a[i]) maxx=max(maxx,f[j]);//上升子序列else if (b[j]==a[i]) f[j]=maxx+1;//公共子序列增加}

代码

#include <cstdio>
int n,a[3001],b[3001],f[3001];
int max(int a,int b){return (a<b)?b:a;}
int main(){scanf("%d",&n); int ans=0;for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) scanf("%d",&b[i]);for (int i=1;i<=n;i++){int maxx=0;for (int j=1;j<=n;j++)if (b[j]<a[i]) maxx=max(maxx,f[j]);else if (b[j]==a[i]) f[j]=maxx+1;}ans=0;for (int i=1;i<=n;i++) ans=max(ans,f[i]);return !printf("%d",ans);
}