Description
Input
Output
Sample Input
5
1 4 5 2 3
3 4 2 1 5
Sample Output
3
Data Constraint
Hint
题解
-
我们考虑在什么情况下，两对点的连线相交
-
就是南北两边它们的顺序相反
-
再考虑如果两条线段已经相交，第三条线段在什么情况下是都与它们相交
-
就是这条线段的两个端点都跨过了原来的两条线段
-
可以发现这道题目就是求最长下降子序列
代码
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #define N 100010 5 #define ll long long 6 using namespace std; 7 ll n,ans,t,l,r,mid,f[N],g[N],a[N]; 8 int main() 9 { 10 scanf("%lld",&n); 11 for (ll i=1;i<=n;i++) scanf("%lld",&a[i]); 12 for (ll i=1;i<=n;i++) scanf("%lld",&t),g[t]=i; 13 for (ll i=1;i<=n;i++) a[i]=g[a[i]]; 14 memset(f,127,sizeof(f)),ans=0; 15 for (ll i=1;i<=n;i++) 16 if (a[i]<f[ans]) ans++,f[ans]=a[i]; 17 else 18 { 19 l=1,r=ans; 20 while (l<r) 21 { 22 mid=(l+r)/2; 23 if (f[mid]<=a[i])r=mid;else l=mid+1; 24 } 25 f[l]=a[i]; 26 } 27 printf("%lld",ans); 28 }