30分求助!!!

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

Limitless_Progress @ 2024-08-03 19:19:02

不知道有啥问题,求调

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int l,r;
    bool operator<(const Node &b) {
        return l<b.l;
    }
};
const int maxn=1e5+10;
int n,dp[maxn];
Node a[maxn];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i].l;
    for(int i=1; i<=n; i++)
        cin>>a[i].r;
    sort(a+1,a+1+n);
    int len=1;
    dp[len]=a[1].r;
    for(int i=2; i<=n; i++) {
        if(dp[len]<a[i].r)
            dp[++len]=a[i].r;
        else {
            int pos=lower_bound(dp+1,dp+1+len,a[i].r)-dp;
            dp[pos]=a[i].r;
        }
    }
    cout<<len<<endl;
    return 0;
}

by weiyiqian @ 2024-08-10 15:38:33

@awawawawa 不能改变原来序列的顺序,公共子序列会受影响。应该是在第二个序列中显示出和第一个序列元素相同的位置,可以看一下第二篇题解。


by Limitless_Progress @ 2024-08-10 19:02:17

@weiyiqian 好的谢谢大佬,我回去改一下


by c20220526 @ 2024-08-18 20:39:00

因为你排序后改变了a.r的相对位置,会影响到LIS的求解


|