P1439 【模板】最长公共子序列
DP的经典例题，适合学完导弹拦截后再来学习
O(\(N^2\))
按照DP常规思考方法
我们令dp[i][j]为P1序列前i个子序列和P2序列前j个子序列的最长公共子序列长度
- 注意，这是一种常见的设dp状态的方式，可以积累）
所以我们进而思考状态转移方程
对于\(dp[i][j]\) 应该和\(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]\)有关
- 无论\(p1[i]\)是否等于\(p2[j],dp[i][j]=dp[i-1][j]\)，同理，\(dp[i][j]=dp[i][j-1]\)
所以\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])\) - 而如果\(p1[i]==p2[j]\) 那么最前面的公共子序列长度即可以+1，所以\(dp[i][j]=dp[i-1][j-1]+1\)
- 而当我们状态转移，状态从（i-1，j）,(i-1,j-1),(i,j-1)这个三个转移过来，这个又从（i-2，j）,(i-2,j-2),(i-1,j-2),(i-2,j-1),(i-2,j-2),(i-1,j-1),(i-1,j-2),(i,j-2)转移，以此类推，所以在状态转移到（i,j）之前，从（1，1）到（i-1，j）都有值，所以才有代码中的循环
综上
$dp[i][j]=max(dp[i-1][j],dp[i][j-1]) $
\(if(p1[i]==p2[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)\)
#include<iostream>
using namespace std;
const int maxn=1e4+10;
int n;
int a[maxn],b[maxn];
int f[maxn][maxn];
int main(){
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i) cin>>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];
return 0;
}
O(\(nlogn\))
在第一种的处理方法中，我们忽略了题目条件中的一个性质：全排列
而此题与导弹拦截有类似之处，我们思考是否有可能将此题转化为最长不下降子序列
在最长不下降子序列中，从一个序列中找一个最长不下降子序列
而此题中是找两个最长公共子序列，所以我们找出的子序列即为另一个序列子序列，那就能解决该问题
（核心思路）
如果我们保证P1序列是上升序列，而从P2序列找到一个最长不下降子序列一定是P1序列的子序列，那么该序列长度即为所求
重新编号就能保证P1序列是上升序列
- 举例
P1:3 2 1 4 5
P2:1 2 3 4 5
重新编号(全排列保证了这样重新编号的合理性)
P1: 1 2 3 4 5
P2: 3 2 1 4 5
- 重新编号也很简单，有map映射即可
- 求最长上升子序列用导弹拦截的方法即可
CODE
#include<bits/stdc++.h>
using namespace std;
map<int,int>m;
int n;
const int maxn=1e5+10;
int a[maxn];
int f[maxn];
int main(){
cin>>n;
for(int i=1;i<=n;++i){
int x;
cin>>x;
m[x]=i;
}
int t=0;
for(int i=1;i<=n;++i){
int x,l=0,r=t;
cin>>x;
x=m[x];
while(l<=r){
int mid=(l+r)>>1;
if(x<f[mid]) r=mid-1;
else l=mid+1;
}
if(l>t) t=l;
f[l]=x;
}
cout<<t<<endl;
return 0;
}