调了半个月了,间歇着调,一直不对

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

LonginusMonkey @ 2022-08-10 22:47:22

向大佬求助!

#include<bits/stdc++.h>
using namespace std;
int arr2[100010];
struct node{
    int a, b; 
};
node arr[100010];
vector<int> vec;
bool cmp(node a, node b) {
    return a.a < b.a;
}
int main() {
    int n;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> arr[i].a;
    }
    for(int i=1; i<=n; ++i) {
        cin >> arr[i].b;
    }
    sort(arr+1,arr+1+n,cmp);
    for(int i=1; i<=n; ++i) {
        arr2[i] = arr[i].b;
    }
    vec.push_back(arr2[1]);
    for(int i=2; i<=n; ++i) {
        if(arr2[i] > vec[vec.size()-1]) {
            vec.push_back(arr2[i]);
        }
        else
        {
            int u = lower_bound(vec.begin(),vec.end(),arr2[i])-vec.begin();
            vec[u] = arr2[i];
        }
    }
    cout << vec.size();
    return 0;
}

by songtj @ 2022-09-11 11:08:24

这道题排序再一个个比对是不行的,要离散化一下,然后就可以变成求最长上升子序列了

可以看一下这个dalao的题解:

链接

这个dalao讲了原理:

链接


|