求调

_HEYTEA_ @ 2024-08-13 15:58:04

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

by haimingbei @ 2024-08-13 16:04:35

@HEYTEA 这题不是dp吗？

by Finner_forgeter @ 2024-08-13 16:07:07

银牌老师教的

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int f[N],a[N],b,ans,n,pre[N],pos;
int main(){
    f[0]=0;a[0]=INT_MIN;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<i;j++)
            if(a[j]<a[i]&&f[i]<f[j]+1){
                f[i]=f[j]+1;
                pre[i]=j;
            }if(ans<f[i]){
                ans=f[i];
                pos=i;
            }
    }vector<int> res;
    while(pos)res.push_back(a[pos]),pos=pre[pos];
    reverse(res.begin(),res.end());
    cout<<ans;
    return 0;
}

by lrmlrm_ @ 2024-08-13 16:10:39

@HEYTEA 谴责

by _HEYTEA_ @ 2024-08-13 16:13:25

@lrmlrm_ 怎么你了

by _HEYTEA_ @ 2024-08-13 16:19:50

@haimingbei 确实是dp，如果用dp的话我写出来的是n方

by haimingbei @ 2024-08-13 16:23:18

@HEYTEA n方能过

by _HEYTEA_ @ 2024-08-13 16:24:48

@haimingbei 我知道能过，但是我还是想把这种写法调出来

by hnzzlxs01 @ 2024-09-11 17:39:18

将

if(b[mid]>a[i])

改为

if(b[mid]>=a[i])

因为最长上升子序列不包括相等的情况