题目链接 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/
转载文章受原作者版权保护。转载请注明原作者出处！