求助

B3637 最长上升子序列

wumoumou_tyxx @ 2024-10-17 20:50:21

rt, 代码:

#include<bits/stdc++.h>
using namespace std;
int a[10000],dp[233333];
int main()
{
   int n,s=1;cin>>n;
   for(int i=1;i<=n;i++)
   cin>>a[i];
   for(int i=1;i<=n;i++)
   {
       int e=1;
       for(int j=1;j<=n;j++)
       {
        if(a[i]>li[e-1])li[e++]=a[i];
        else continue;
    }
    if(e-1>s)s=e-1;
   }

    cout<<s;
}

by wumoumou_tyxx @ 2024-10-17 20:53:01

0分


by Ff472130 @ 2024-10-17 21:05:31

#include<bits/stdc++.h>
using namespace std;
int a[10000],dp[233333];
int main()
{
   int n,ans=0;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-1;j++)
       {
        if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);;
    }
   }
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    cout<<ans;
}

by Civilight_Eterna @ 2024-10-17 21:07:43

@wumoumou_tyxx 下次不要粘CE代码了,你看一下上一个人的做法


by Civilight_Eterna @ 2024-10-17 21:09:24

题解很简单明了了


by wumoumou_tyxx @ 2024-10-17 21:10:54

@xionghaoran123 ??? 我自己写的


by wumoumou_tyxx @ 2024-10-17 21:11:50

@xionghaoran123 @Ff472130 关了


by Civilight_Eterna @ 2024-10-17 21:12:32

ee


by mo_mo_yu0_0 @ 2024-10-30 22:20:18

@Ff472130 其实可以二分


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,a,r[5015],ans;
int main(){
    cin>>n;
    while(n--){
        cin>>a;
        int p=lower_bound(r,r+ans+1,a)-r;
        if(p>ans)ans=p;
        r[p]=a;
    }
    cout<<ans;
}

|