爆零，玄关，求调

Liuzr20 @ 2024-08-27 09:50:56

#include<bits/stdc++.h>
using namespace std;
long long n;
int a[10005],b[10005],c[10005]={0},d[10005]={0};
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[j]=max(d[j-1],c[j]);
            if(a[i]==b[j]){
                d[j]=max(d[j],c[j-1]+1);
            }
        }
    }
    cout<<d[n]<<endl;
    return 0;
}

by Dress @ 2024-08-27 09:58:02

O(n^2)过不了10^5是正常情况，可以试一下O(nlogn)的算法。 @Liuzr20

by hhztl @ 2024-08-27 09:58:08

@Liuzr20 你c[j]是干啥用的

by Dress @ 2024-08-27 10:00:57

@Liuzr20

#include<bits/stdc++.h>
#define N 100005
using namespace std;
template<typename type>
inline void read(type &x)
{
    x=0;static bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1)//0为空格，1为换行
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}
int n,p1[N],p2[N];
int dis[N],b[N],f[N],l;
int main(){
    ios::sync_with_stdio(false);
    read(n);
    for(int i=1;i<=n;i++){
        read(p1[i]);
        dis[p1[i]]=i;
    }
    for(int i=1;i<=n;i++){
        read(p2[i]);
    }
    for(int i=1;i<=n;i++){
        if(dis[p2[i]]>b[l]){
            b[++l]=dis[p2[i]];
            f[i]=l;
            continue;   
        }   
        int k=lower_bound(b+1,b+1+l,dis[p2[i]])-b;
        b[k]=dis[p2[i]];
        f[i]=k;
    }
    cout<<l;
    return 0;
}

参考一下我的，求关QWQ

by Liuzr20 @ 2024-08-27 10:02:33

@Dress 大佬，谢谢

但是，二分的程序，在下请教

by Liuzr20 @ 2024-08-27 10:04:56

@hhztl

c[j]好像是没用

by Liuzr20 @ 2024-08-27 10:07:13

@Dress

已关