初学者,20求调

P1439 【模板】最长公共子序列

jqdlk @ 2024-03-04 09:50:13

#include<bits/stdc++.h>
#define MAX_N 100010
using namespace std;
int dp[MAX_N];
int a[MAX_N], b[MAX_N];
int now = 0;
int bound(int x)
{
    int L = 1, R = now;
    while (L < R)
    {
        int mid = (L + R) >> 1;
        if (b[dp[mid]] > b[x])
            R = mid;
        else
            L = mid + 1;
    }
    return L;
}
int main()
{
    int n;
    int temp;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> temp;
        b[temp] = i;
    }
    for (int i = 1; i <= n; i++)
        {
        if (b[a[i]] > b[dp[now]])
            dp[++now] = a[i];
        else
            dp[*lower_bound(dp+1,dp+now,a[i])] = a[i];
        }
    cout << now;
}

看到题解有个用二分(上面有大佬写的bound函数),但为什么我差不多的思路,用的是lower_bound就只有20,感谢


|