40pts，单调栈做法

heyuguo @ 2023-09-28 21:08:32

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005]={-1},f[100005],s[100005],top=0,ans;//s:栈 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        f[i]=1;
    memset(s,0x3f,sizeof s);
    s[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>s[top])
            s[++top]=a[i],f[i]=top;
        else
        {
            long long l=0,r=top+1,mid=(l+r)>>1;
            while(l+1<r)
            {
                if(s[mid]>=a[i])
                    r=mid-1;
                else
                    l=mid;
                mid=(l+r)>>1;
            }
//          for(int i=1;i<=top;i++)
//          {
//              cout<<s[i]<<' ';
//          }cout<<'\n';
//          cout<<'l'<<l<<'\n';
            f[i]=l+1;

            s[l+1]=min(s[l+1],a[i]);
//          for(int i=1;i<=top;i++)
//          {
//              cout<<s[i]<<' ';
//          }cout<<'\n';
//          top=max(top,l+1);
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

by Elysian_Realm @ 2023-09-29 23:21:16

稍微修改了一下二分查找的部分 修改前：

long long l=0,r=top+1,mid=(l+r)>>1;
while(l+1<r){
    if(s[mid]>=a[i]) r=mid-1;
    else l=mid;
    mid=(l+r)>>1;
}

修改后：

long long l=0,r=top,mid=(l+r)>>1;
while(l<r){
   if(l==r-1){
    if(s[r]<a[i]) l=r;
        break;
   }  
    if(s[mid]>=a[i]) r=mid-1;
    else l=mid;
    mid=(l+r)>>1;
}

已AC私题(记录:https://www.luogu.com.cn/record/126621502

by craftmine @ 2023-09-30 12:02:20

mid=l+(r-l)>>1

防止越界

还有用dp可能更好点：

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

by BensonChen @ 2023-10-04 10:40:00

#include <bits/stdc++.h>

using namespace std;

int n,A[5140],dp[5140];

int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>A[i];
    }
    for (int i=1;i<=n;i++){
        dp[i]=1;
        for (int j=1;j<=i;j++){
            if(A[j]<A[i]&&dp[i]<dp[j]+1)dp[i]=dp[j]+1;
        }
    }
    cout<<dp[n];
    return 0;
}

我这dp咋20分。。。