洛谷P1439 最长公共子序列 - hash - dp - 贪心

因为是两串排列，所以两串值相同位置不同
那么公共子序列要求的就是值相同，而“子序列”要求的是值的位置上升
那么把ab串联系起来，b和a相同的值，位置不同。
设\(fb_i\) 为值为bi的数在a串中的位置，显然已经满足相同
那么只要取出一个最长子序列即可，若f值上升，则位置递增，则说明这些bi在a中可以构成一个子序列
注意数组下标代表的是长度，存的值是结尾的权值，二分查找到一个下标，直接替换就好了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
const int MAXN = 100000 + 10;
int f[MAXN],n,a[MAXN],vis[MAXN],m[MAXN],b[MAXN],fm[MAXN];
int q,fa[MAXN],last[MAXN],depth[MAXN],len;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        m[a[i]] = i;
    }
    for(int i=1; i<=n; i++) {
        cin >> b[i];
        fm[i] = m[b[i]];
    }
    f[1] = fm[1];
    len = 1;
    for(int i=2; i<=n; i++) {
        if(fm[i] > f[len]) f[++len] = fm[i];
        else {
            int temp = lower_bound(f+1, f+len+1, fm[i]) - f;
            f[temp] = fm[i];
        } 
    }
    cout << len;
    return 0;
}

洛谷P1439 最长公共子序列 - hash - dp - 贪心

原文：https://www.cnblogs.com/Zolrk/p/9898178.html