why

B3637 最长上升子序列

yyc1117 @ 2024-07-18 09:32:19

提交记录传送门代码：

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

之前有一种方法AC了，后面用这种方法变成了40分o(╥﹏╥)o

by shenghongqian @ 2024-07-19 23:34:24

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