题目链接 P1439
LIS(Longest Increasing Subsequence)(最长递增子序列)
LCS(Longest Common Subsequence)(最长公共子序列)
简朴的DP
点击查看代码
#include<iostream>
using namespace std;
const int N=1010;
int n;
int a[N],b[N];
int f[N][N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i="1;i<=n;i++)scanf("%d",&b[i]);" { j="1;j<=n;j++)" f[i][j]="max(f[i-1][j],f[i][j-1]);" if(a[i]="=b[j])" } cout<<f[n][n]<<endl; return 0; < code></=n;i++)scanf("%d",&a[i]);></iostream>
离散化
题中所说每个序列是1-N的一个排列,所以可以知道,P1和P2两个序列 元素相同,排列不同 。
那么我就可以利用离散化(叫映射更合理一点?),将P1中的元素(记为a1,a2,a3……an)映射为(1,2,3,……,n)。
很明显,这是一个严格单调递增符合题条件的序列。
利用同样的映射关系,把P2序列也转化一下,将转化后的序列记为(b1,b2,b3……bn)。
因为P1严格单调递增,那么,求映射后的P1,P2的LCS,不就是求P2的LIS嘛?
栈的使用
求一个序列的LIS,也可以DP,但因为时间复杂度也是n的平方,所以我们使用二分。
利用一个单调递增的栈,不断更新栈中序列,最后留下的序列的大小就是原序列LIS的大小。但是,留下的序列 不是LIS。
栈中序列虽然递增,但是每个元素在原串中对应的位置其实可能是乱的,那为什么这个栈还能用于计算最长子序列长度?
实际上这个栈不用于记录最终的最长子序列,而是以stk[i]结尾的子串长度最长为i或者说长度为i的递增子串中,末尾元素最小的是stk[i]。
理解了这个问题以后就知道为什么新进来的元素要不就在末尾增加,要不就 替代第一个大于等于它元素的位置(lower_bound函数的作用)
这里的 替换就蕴含了一个贪心的思想,对于同样长度的子串,我当然希望它的末端越小越好,这样以后我也有更多机会拓展
最终代码
点击查看代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100010;
int map[N],a[N],b[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) { scanf("%d",&a[i]); map[a[i]]="i;" } for(int i="1;i<=n;i++)" scanf("%d",&b[i]); b[i]="map[b[i]];" vector<int>stk;
stk.push_back(b[1]);
for(int i=2;i<=n;i++) { if(b[i]>stk.back())
{
stk.push_back(b[i]);
}else
{
*lower_bound(stk.begin(),stk.end(),b[i])=b[i];
}
}
cout<<stk.size()<<endl; return 0; } < code></stk.size()<<endl;></=n;i++)></=n;i++)></algorithm></vector></iostream>
Original: https://www.cnblogs.com/Az1r/p/16667606.html
Author: 江水为竭
Title: 最长公共子序列
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/686294/
转载文章受原作者版权保护。转载请注明原作者出处!