40分求条

NOI_AK_I @ 2024-08-06 16:35:22

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10086;
int n,m,l,r,len=1,mid,a[N],dp[N]={INT_MAX};
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>=dp[len]) dp[++len]=a[i];
        else
        {
            l=1,r=len;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(a[i]>dp[mid]) l=mid+1;
                else r=mid-1;
            }
            dp[mid]=a[i];
        }
    }
    cout<<len;
}

by RedStoneShark @ 2024-08-06 16:53:23

不用二分，用板子就行了

by NOI_AK_I @ 2024-08-06 19:13:19

@贺文骏RedShark wcnm

by NOI_AK_I @ 2024-08-06 19:14:51

@贺文骏RedShark cnmd

by RedStoneShark @ 2024-08-06 19:15:00

真的，你别不信，ACCode：

#include<iostream>
using namespace std;
int n,a[5010],dp[5010];
int main(){
    cin>>n;
    dp[1]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int ans=-0x7fffffff;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

by RedStoneShark @ 2024-08-06 19:15:22

@Danny301

by NOI_AK_I @ 2024-08-06 19:16:00

@xxxasybt2023 cnmd

by RedStoneShark @ 2024-08-06 19:16:02

不是我怎么了

by NOI_AK_I @ 2024-08-06 19:17:31

我说验证码是cnmd你信吗

by NOI_AK_I @ 2024-08-06 19:23:29

@贺文骏RedShark .--/-.-./-./-- 这里