題目描述 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[i][j]維護的是A中前i個,B中以第j個結尾的最長公共上升子序列的長度

看清楚哈，i在A中的概念是前i個，意思是并不要求一定要是i結尾

B中的j是必須是j結尾的

然后怎么轉移呢?

首先，當A[i]!=B[j]的時候，因為B[j]必須要用來結尾，所以f[i][j]=f[i-1][j]

當A[i]==B[j]的時候，會有f[i][j]=max(f[i-1][k])+1
其中B[k] < A[i] 且 k < j

因為B[k] < A[i],所以f[i][j]肯定是可以從f[i-1][k]轉移過來的

其次，因為A[i]要和B[j]組成一起，所以是從f[i-1]里面找，而不是在f[i]里面找，再其次，B[j]是后來要被使用的，所以k < j也是肯定的

現在問題就是，如果k是枚舉，那么復雜度就是O(n^3)了，就會TLE

所以必須用O(1)的方法，求出k

再看到是B[k] < A[i],但是i是第一層循環，，所以我們只要在第二層循環里面，維護k,使得B[k] < A[i]，且f[i-1][k]是最大的
.
.
.
.
.

程序：

#include<iostream> using namespace std; int f[3001][3001],a[3001],b[3001]; int main() {int n;cin>>n;for (int i=1;i<=n;i++) cin>>a[i];for (int i=1;i<=n;i++) cin>>b[i];a[0]=b[0]=-2147483647;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<=n;j++){if (a[i]==b[j]) f[i][j]=val+1; else f[i][j]=f[i-1][j];if (b[j]<a[i]) val=max(f[i-1][j],val);}}int ans=0;for (int i=1;i<=n;i++) ans=max(f[n][i],ans);cout<<ans; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499891.html

總結

以上是生活随笔為你收集整理的CODEVS 1408 最长公共子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

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