最长公共上升子序列
题目 最长公共上升子序列
思路分析
这是两个经典DP模型的结合版：
LIS(最长上升子序列，Longest Increasing Subsequence)
for(j=1;j<i;j++) if(a[j]<a[i]) f[i]=f[j]+1
LCS(最长公共子序列，Longest Common Subsequence)
f[i][j]=max({f[i][j-1],f[i-1][j],f[i-1][j-1]+(a[i]==b[j])})
LCIS(最长公共上升子序列，Longest Common Increasing Subsequence)
LCIS 也是一个相当经典的DP模型，他的 状态分析 是 LIS 与 LCS 的结合
首先两个序列所以用f[i][j]来表示状态
不过现在的f[i][j]的含义有所变化——考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案
（因为在公共子序列的基础上加了一个上升的限制 所以现在不能每个都选了 是否能选得根据上一个位置是什么决定 这个上一个位置就存在b[j]当中）
属性自然是max
状态转移
首先看a[i]位置可不可选 如果不可选的话状态应该是从f[i-1][j]转移过来
如果a[i]可选 还得看它到底从哪个位置转移过来 如果a[i-1]等于b[1]那么就应该从f[i-1][1]转移过来 同理 如果等于b[k]就得从f[i-1][k]转移过来
由此划分出两个不重不漏的子集
不包含a[i]的子集，最大值是f[i - 1][j]；
包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：
子序列只包含b[j]一个数，长度是1；
子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；
…
子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；
由此写出朴素做法：
#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],b[N];
int f[N][N];
int n;
int main()
{
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++){
for(int j=1;j<=n;j++){
f[i][j]=f[i-1][j];
if(a[i]==b[j]){
for(int k=0;k<j;k++){
if(b[j]>b[k]){
f[i][j]=max(f[i][j],f[i-1][k]+1);
}
}
}
}
}
int res=0;
for(int i=0;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
return 0;
}
tle了
我们可以观察到，对于第二种状态转移：
\(f_{i,j}=max(f_{i,j},f_{i−1,k}+1) k∈[0,j−1],a_i=b_j,b_j>b_k\)每次用到的 状态 都是第 i - 1 个阶段的
因此我们可以用一个变量，存储上一个阶段的能够接在 a[i] 前面的最大的状态值
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
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)
{
int maxv = 1;
for (int j = 1; j <= n; ++ j)
{
f[i][j] = f[i - 1][j];
if (b[j] == a[i])
f[i][j] = max(f[i][j], maxv);
if (b[j] < a[i])
maxv = max(maxv, f[i - 1][j] + 1);
}
}
int res = 0;
for (int i = 0; i <= n; ++ i)
res = max(res, f[n][i]);
cout << res << endl;
return 0;
}
同类题型
视频讲解
⬅️ 最长上升子序列模型练习 🏠 00-刷题理模型 ➡️ 最长公共子序列
💬 评论