竞赛讨论区 > A题 我的最长上升子序列有什么问题吗 为什么只能过30%?
头像
ambition.xx
编辑于 2022-04-28 22:57
+ 关注

A题 我的最长上升子序列有什么问题吗 为什么只能过30%?

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename T>
void print(vector<T> &arr){
	for(auto &a : arr){
		cout << a << " ";
	}
	cout << endl;
}
int main() {
	//freopen("in1.txt", "r", stdin);
	int n;
	while(cin >> n){
		vector<int> a(n, 0), b(n, 0);
		for(auto &e : a) scanf("%d", &e); //cin >> e;
		for(auto &e : b) scanf("%d", &e); //cin >> e;
		map<int, int> mp;
		for(int i = 0; i < n;i++){
			mp[b[i]] = i;
		}
		int cnt = 0;
		for(int i = 0; i < n; i++){
			a[i] = mp[a[i]];
		}
		vector<int> dp(1, INT_MIN);
        for(auto n : a){
            if(dp.back() < n){
                dp.push_back(n);
            } else {
                int pos = lower_bound(dp.begin(), dp.end(), n) - dp.begin();
                dp[pos] = n;
            }
        }
		printf("%d\n", n - (dp.size() - 1));
	}
	return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐