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,感谢