P1439 【模板】最长公共子序列
题目链接 P1439
LIS(Longest Increasing Subsequence)(最长递增子序列)
LCS(Longest Common Subsequence)(最长公共子序列)
简朴的DP
求LCS标准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]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
{
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
}
cout<<f[n][n]<<endl;
return 0;
}
离散化
题中所说每个序列是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
求一个序列的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;
}