TLE，如何添加二分，蒟蒻求助

cxzhyf @ 2023-06-02 19:27:57

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[10006],b[10006],dp[10006][10006];
int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n;i++) cin>>b[i];
    for(i=1;i<=n;i++) 
        for(j=1;j<=n;j++){
            if(dp[i][j]) continue;
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    for(i=1;i<=n;i++) 
        for (j=1;j<=n;j++) ans=max(ans,dp[i][j]);
    cout<<ans;
    return 0;
}

by kelanjie @ 2023-06-02 19:45:24

@cxzhyf 题解有。一言难尽

by zhlzt @ 2023-06-02 20:28:48

@cxzhyf 无法添加二分，正解需要借助 STL map。p

by Miss_SGT @ 2023-07-06 10:57:01

@Special_Tony 1~n的排列，要啥map

by Grow2011 @ 2023-07-10 11:23:32

@Special_Tony要map干嘛？我这样不也过了？

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,b[100005],x[100005],op;
struct node{
    int x,id;
}a[100005];
bool cmp(node a,node b){
    return a.x<b.x;
}
int LIS(int a[],int n){
    int lis[100005],len=0;
    lis[1]=a[1];
    len++;
    for(int i = 2;i<=n;i++){
        int pos = lower_bound(lis+1,lis+len+1,a[i])-lis;
        lis[pos]=a[i];
        len=max(len,pos);
    }
    return len;
}
int find(int x){
    int l = 1,r = n;
    while(l<r){
        int mid = (l+r)/2;
        if(a[mid].x<x)l=mid+1;
        else r = mid;
    }
    return l;
}
signed main(){
    cin >> n;
    for(int i = 1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i;
    for(int i = 1;i<=n;i++)scanf("%d",&b[i]);
    sort(a+1,a+n+1,cmp);
    for(int i = 1;i<=n;i++){
        int pos = find(b[i]);
        if(a[pos].x==b[i]){
            x[++op]=a[pos].id;
        }
    }
    cout << LIS(x,op);
    return 0;
}