个人认为此题很值得好好学习,在这里记录一下思考过程,以及不同的思路
想法一:动态规划-公共子序列
参考题目4555.公共子序列
https://www.acwing.com/problem/content/4558/
我想用dp[i][j]
二维数组来记录,但很明显,这道题N=10e6,二维数组连开都开不出来…放弃
想法二:使用辅助下标数组转化成最长上升子序列
我的理解过程-先想象成一个字符数组
A :3 2 1 4 5
B :1 2 3 4 5
不妨重新标个号:把3改成a,把2改成b....那么:
A : a b c d e
B : c b a d e
这样标号之后,最长公共子序列的长度不会发生变化,但是出现了一个性质:
两个序列的最长公共子序列一定是A的子序列,而A本身就是单调递增的,所以这个子序列也是单调递增的。
换句话说,只要这个子序列在B种单调递增,它就是A的子序列。
所以就转化为了求B的最长递增子序列问题。
进一步理解
引入一个下标数组
在输入数组a时,其实没有必要存下来a的内容,只需要存每个元素的下标,形成一个下标数组c
然后读取数组b,把b中每个元素x转化成它在c中的下标,也就是x这个值在原数组a中的位置
想法三:使用动态规划求解最长上升子序列O(N^2)
虽然但是,仍然会超时,先放上代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int b[N],idx[N];
int dp[N];//dp[i]表示以b[i]作为结尾的最长递增子序列的长度
int main(){
int n;
cin>>n;
int tmp;
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
idx[tmp]=i;//存下来数组a的元素下标
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
b[i]=idx[b[i]];
}
//通过引入这个下标数组,对数组b进行变换,让b中存的是每个元素在第一个数组中出现的位置,如果没出现过就是0
int maxlength=0;//最大上升子序列长度
for(int i=1;i<=n;i++){
if(b[i]==0) continue;
dp[i]=1;//先全部初始化为1,即只有自己的长度
for(int j=1;j<i;j++){
if(b[j]==0) continue;
if(b[j]<b[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
maxlength=max(maxlength,dp[i]);
}
cout<<maxlength<<endl;
return 0;
}
想法四:贪心+二分O(nlogn)
思路
代码
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e6+10;
int b[N],idx[N];
vector<int> tmparr;
int main(){
int n;
cin>>n;
int tmp;
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
idx[tmp]=i;//存下来数组a的元素下标
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
b[i]=idx[b[i]];
}
for(int i=1;i<=n;i++){
if(b[i]==0) continue;
if(tmparr.empty() || b[i]>tmparr.back()){
tmparr.push_back(b[i]);
}
else{
int pos=lower_bound(tmparr.begin(),tmparr.end(),b[i])-tmparr.begin();
tmparr[pos]=b[i];//替换
}
}
cout<<tmparr.size()<<endl;
return 0;
}