1 条题解

  • 1
    @ 2025-4-26 12:34:29
    #include <bits/stdc++.h>
    #define endl '\n'
    using namespace std;
    
    typedef long long ll;
    
    const int N =100010;
    int a[N], b[N], c[N], dp[N];
    int n;
    
    int main() {
    	cin >> n;
    	for (int i = 1; i <= n; i++) {
    		cin >> a[i];
    		c[a[i]] = i;
    	}
    	for (int i = 1; i <= n; i++)
    		cin >> b[i];
    
    	int len = 1;
    	dp[1] = c[b[1]];
    
    	for (int i = 2; i <= n; i++) {
    		if (c[b[i]] > dp[len]) {
    			dp[++len] = c[b[i]];
    		} else {
    			int l = 1, r = len;
    			while (l <= r) {
    				int mid = (l + r) / 2;
    				if (dp[mid] >= c[b[i]]) {
    					r = mid - 1;
    				} else {
    					l = mid + 1;
    				}
    			}
    			dp[l] = c[b[i]]; 
    		}
    	}
    	cout << len << endl;
    	return 0;
    }
    

    信息

    ID
    5497
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    62
    已通过
    20
    上传者