2185 最長公共上升子序列

?時間限制: 1 s ?空間限制: 32000 KB ?題目等級 : 鉆石 Diamond 題目描述?Description

熊大媽的奶牛在小沐沐的熏陶下開始研究信息題目。小沐沐先讓奶牛研究了最長上升子序列，再讓他們研究了最長公共子序列，現在又讓他們要研究最長公共上升子序列了。
小沐沐說，對于兩個串A，B，如果它們都包含一段位置不一定連續的數字，且數字是嚴格遞增的，那么稱這一段數字是兩個串的公共上升子串，而所有的公共上升子串中最長的就是最長公共上升子串了。
奶牛半懂不懂，小沐沐要你來告訴奶牛什么是最長公共上升子串。不過，只要告訴奶牛它的長度就可以了。

輸入描述?Input Description

第一行N，表示A，B的長度。
第二行，串A。
第三行，串B。

輸出描述?Output Description

輸出長度。

樣例輸入?Sample Input

4
2 2 1 3
2 1 2 3

樣例輸出?Sample Output

2

數據范圍及提示?Data Size & Hint

1<=N<=3000，A，B中的數字不超過maxlongint

/*思路：f[]數組里面儲存著到b的第i項，a從1--n的且以b[i]結尾的最長公共上升子序列長度，問題一： dp方程說明：if(a[i]>b[j]&&maxx<f[j])更新可以用于更新b序列與a序列前i位的最長長度的最大值 maxx=f[j];if(a[i]==b[j]) f[j]=maxx+1;因為j是內循環，所以如果maxx被更新了，則現在的b[j]是等于a[i]，一定比更新maxx的bj大，所以可以直接加。 問題二： 為什么可以改為一維？：類似于背包問題，假如用f[i][j]表示到了a的第i項（不一定為ai結尾），以b的第j項結尾的最長長度，那么 f[i][j]，如果ai!=bj,那么f[i-1][j]就是最佳選擇，而且一定比f[i-2][j]優，而當ai==bj的時候，我們用maxx更新f[i][j]，與之前的無關，那么可見F[i][j]只與i-1的值有關，那么就可以用一唯數組了。 */ #include<iostream> using namespace std; #include<cstdio> const int N=3001; int a[N],b[N],f[N],maxx; int main() {ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;++i)cin>>b[i];for(int i=1;i<=n;++i){maxx=0;for(int j=1;j<=n;++j){if(a[i]>b[j]&&maxx<f[j])maxx=f[j];if(a[i]==b[j]) f[j]=maxx+1;}}maxx=0;for(int i=1;i<=n;++i)/*因為對于f[]數組我們是規定了結尾，所以f[n]不一定是最優值，所以要全搜索一次*/maxx=max(f[i],maxx);cout<<maxx<<endl;return 0; } View Code

?

轉載于:https://www.cnblogs.com/c1299401227/p/5323569.html

總結

以上是生活随笔為你收集整理的codevs 2185 最长公共上升子序列--nm的一维求法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。