求助QAQ

ycyxh1 @ 2024-07-08 16:50:07

#include<bits/stdc++.h>
using namespace std;
int p1[100001],p2[100001];
int a[100001];
int n,tot=0;
int work(int x){
    int l=1,r=tot,ans;
    while(l<=r){
        int mid=l+r>>1;
        if(a[mid]>x){
            r=mid-1;
            ans=mid;
        }
        else{
            l=mid+1;
            ans=mid+1;
        }
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&p1[i]);
    } 
    for(int i=1;i<=n;i++){
        scanf("%d",&p2[p1[i]]);
    }
    for(int i=1;i<=n;i++){
        if(p2[i]>a[tot]){
            a[++tot]=p2[i];
        }
        else{
            a[work(p2[i])]=p2[i];
        }
    }
    printf("%d",tot);
    return 0;
}

by ChampionCyan @ 2024-07-08 16:51:40

@ycyxh1

那不对，要用dp。

hack:

样例(bushi

我过了嘲讽你。

by ycyxh1 @ 2024-07-08 16:56:11

@ChampionCyan

你信不信我jb你，哪里样例过不了了，每次发帖都恶意回复有意思吗

by ChampionCyan @ 2024-07-08 16:57:18

@ycyxh1

有一说一，这确实是dp，我现在告诉你你这样不行还说我恶意回复

by ycyxh1 @ 2024-07-08 16:58:04

@ChampionCyan

可以不用dp，用二分也可以

by ChampionCyan @ 2024-07-08 16:58:05

@ycyxh1

那你别听我说的，有本事别用dp？

by ChampionCyan @ 2024-07-08 16:59:24

@ycyxh1

6，正解难道不是dp+二分？那二分也行有本事别用dp纯二分？

by meifan666 @ 2024-07-08 16:59:28

@ycyxh1 懒得纠错了，我的代码和你很像，自己找找哪不对

#include<bits/stdc++.h>
using namespace std;
int n,t=1;
int a[100100],b[100100],ans=1,k[100100];
int erfen(int l,int r,int key)
{
    int ans=1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(k[mid]<key)l=mid+1;
        else
        {
            ans=mid;
            r=mid-1;
        }
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[a[i]]=t++;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=b[a[i]];
    }
    k[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>k[ans])
        {
            k[++ans]=a[i];
        }
        else
        {
            k[erfen(1,ans,a[i])]=a[i];
        }
    }
    printf("%d",ans);
    return 0;
}

by ChampionCyan @ 2024-07-08 17:00:14

哦，好像确实可以

by ycyxh1 @ 2024-07-08 17:00:58

@ChampionCyan

。。。。。。

by ChampionCyan @ 2024-07-08 17:00:58

那你自己调吧，不管了，顺便道个歉。