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的求解