P1439 最长公共子序列

最长公共子序列

动态规划

通过不断改变数组状态，达到理想状态，要先找到推导的动态转移方程。

动态规划：现在决定未来，未来与过去无关。

转化

通过对题目的观察，可以发现只给了两个字符串，所以可以将问题进行转换，转换成最长不下降序列。

以第一个序列为主，转化第二个序列。

现在 第一个序列为：$1,2,3,4,$……
而 第二个序列却是乱序，通过一的转换。

问题就变成了求最长不下降子序列。

代码实现

传送门

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
using namespace std;
const int m_m=100001; 
int a[m_m],b[m_m],x_x[m_m],f[m_m];
int o_o=0;
int main(){
  int n;
  cin>>n;//长度 
  for(int i=1;i<=n;i++){
    cin>>a[i];x_x[a[i]]=i;//便利初值，即将第一字符串变成123…… 
  }
  for(int i=1;i<=n;i++){
    cin>>b[i];f[i]=0x7f7f7f7f;//设置最大值，方便找最小值 
  }
  f[0]=0;
  for(int i=1;i<=n;i++){
    int l=0,r=o_o,n_n;
    if(x_x[b[i]]>f[o_o])f[++o_o]=x_x[b[i]];
    else{
      while(l<r){ //二分策略 
          n_n=(l+r)/2;//中间的数 mid 
          if(f[n_n]>x_x[b[i]])r=n_n;//右边界便利 
        else l=n_n+1;//左边界便利 
      }
      f[l]=min(x_x[b[i]],f[l]);//搜索最长长度 
      }
    }
    cout<<o_o;//输出最长上升序列 
    return 0;//完美收官@*_*@ 
}