TLE求助

jyz2012 @ 2023-06-03 19:35:23

#include <iostream>
using namespace std;
typedef long long ll;
int n;
int ans=0;
int a[5001];

int f(int i){
    int maxx=0;
    for(int j=i+1;j<n;j++){
        if(a[j]>a[i]){
            int fj=f(j);
            if(fj>maxx){
                maxx=fj;
            }
        }
    }
    return maxx+1;
} 
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        int fi=f(i);
//      cout <<"f("<<i<<")="<<fi<<endl;
        if(fi>ans){
            ans=fi;
        }
    }
    cout<<ans<<endl;
    return 0;
}

by _7Mr @ 2023-06-07 16:05:21

@jyz2012 考虑dp

by jyz2012 @ 2023-06-20 20:56:14

@luozhih 加上备忘就A了。。。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int n;
int ans=0;
int a[5001];
int memo[5001];

int f(int i){
    if(memo[i]!=-1)return memo[i];
    int maxx=0;
    for(int j=i+1;j<n;j++){
        if(a[j]>a[i]){
            int fj=f(j);
            if(fj>maxx){
                maxx=fj;
            }
        }
    }
    return memo[i]=maxx+1;
} 
int main(){
    memset(memo,-1,sizeof memo);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        int fi=f(i);
//      cout <<"f("<<i<<")="<<fi<<endl;
        if(fi>ans){
            ans=fi;
        }
    }
    cout<<ans<<endl;
    return 0;
}

hhh

by terryjiang @ 2023-06-20 21:39:50

@jyz2012

《这是一个简单的动规板子题》

by lys2012070706 @ 2023-07-10 16:23:51

不用备忘

#include<bits/stdc++.h>
using namespace std;
int f[10001],maxn=-9999999,a[10001],x,y,z,i,j;
int main()
{
    cin>>x;

    for(i=1;i<=x;i++)
    {
        cin>>a[i];
        f[i]=1;
    }

    for(i=1;i<=x;i++)
        for(j=i+1;j<=x;j++)
        {
            if(a[i]<a[j])f[j]=max(f[j],f[i]+1);
        }
    for(i=1;i<=x;i++)
    {
        if(f[i]>maxn)maxn=f[i];
    }
    cout<<maxn;
}