#动态规划，线性动态规划#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\le 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);
}

这篇关于#动态规划，线性动态规划#codevs 2185 CH 5101 LCIS 最长公共上升子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---