今日复习了朴素LCS,学习了LCS优化，以及LCIS 最长上升公共子序列
P1439 最长公共子序列
题目描述
给出 1,2,…,𝑛 的两个排列 𝑃1 和 𝑃2 ，求它们的最长公共子序列。
输入格式
第一行是一个数 𝑛。
接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。
输出格式
一个数，即最长公共子序列的长度。
- 对于 100% 的数据， 𝑛≤1e5。
由上述数据可知，朴素算法会被卡，因此要根据全排列性质进行优化，因为两个序列只是数的位置不同，因此可以用离散化方式将第一个序列映射成单调的1,2,3,4....n则只需要在第二个序列在此映射关系下的单调序列的最长长度即可,即可转换成LIS问题，LIS优化方法可以做到nlogn
#include <iostream>
using namespace std;
const int N=1e5+7;
int a[N],b[N],g[N],map[N],n;//f[i]表示长度位i结尾最小的值
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i],map[a[i]]=i;//离散化映射
for(int i=0;i<n;i++) cin>>b[i];
int len=0;
for(int i=0;i<n;i++){
int t=map[b[i]];
int pos=lower_bound(g+1,g+len+1,t)-g;
g[pos]=t;
len=max(pos,len);
}
cout<<len;
return 0;
}Acwing 3510. 最长公共子序列
同理只需要把第二个序列在第一个序列中不存在的去掉即可
Acwing 272. 最长公共上升子序列
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列 A 和 B 的长度均不超过 3000。
输入格式
第一行包含一个整数 N，表示数列 A，B 的长度。
第二行包含 N 个整数，表示数列 A。
第三行包含 N 个整数，表示数列 B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤𝑁≤3000,序列中的数字均不超过 2^31−1。
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2朴素写法:
首先更据LIS,和最长公共子序列,可以将集合f[i,j]表示为由a的前i个，b的前j个且以b[j]结尾的公共上升子序列长度，属性为最大值
划分依据为a[i]是否被包含，不包含a[i]就是f[i-1,j]
包含a[i]则必然有a[i]=b[j]
可以将包含a[i]的情况按照序列倒数第二个数进行划分,为空(只有一个)，为b[1------j-1]
将f[i,k]+1(以b[j]结尾的一个加上)取最大值即可
最后枚举f[n][k]枚举每个b[k]结尾的最长公共子序列长度取最大即可
#include <iostream>
#include <algorithm>
using namespace std;
const int N=3050;
int a[N],b[N],f[N][N];//f[i][j]表示以a中前i个,b中前j个且以b[j]结尾的公共子序列长度的最大值
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=n;j++) cin>>b[j];
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]){
f[i][j]=max(f[i][j],1);//若从上面继承的为0,就取空值1,表示一个元素
for(int k=1;k<j;k++)
if(b[k]<b[j])//注意用b[1到j-1]更新时要保证小于b[j]才能继承
f[i][j]=max(f[i][j],f[i][k]+1);
}
}
int res=0;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res;
return 0;
}但是当有极限情况时，也就是3000个数每个都相同时，会跑满三重循环导致超时，因此要进行优化,因此把相等条件替换进if表达式,因此b[k]<a[i]与b[j]无关，只与j-1有关
因此用一个变量maxv在遍历前j-1时存最大值对代码做等价变形即可
#include <iostream>
#include <algorithm>
using namespace std;
const int N=3010;
int a[N],b[N],f[N][N];//f[i][j]表示以a中前i个,b中前j个且以b[j]结尾的公共子序列长度的最大值
int g[N][N];//满足b[j]<a[i]的f[i][j]+1的最大值
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=n;j++) cin>>b[j];
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(a[i]==b[j]) f[i][j]=max(f[i][j],maxv);
if(b[j]<a[i]) maxv=max(maxv,f[i][j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res;
return 0;
}
