求助记忆化搜索！！

Daniel_yao @ 2022-10-08 16:01:51

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007
#define inf 1e6

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 5100;

int n = read(), a[N], ans, maxi, f[N]; 

int dfs(int x) {//前x个数的最大长度ans 
    if(f[x] != -1) return f[x];
    int res = 1;
    for (int j = 1; j < x; j++) {
        if(a[j] < a[x]) res = max(res, dfs(j) + 1);
    }
    return f[x] = res;
}

signed main() {
    memset(f, -1, sizeof f);
    For(i,1,n) a[i] = read();
    a[n + 1] = inf; 
    cout << dfs(n) << '\n';
  return 0;
}

by anonymous_letter @ 2022-10-08 16:38:44

// Author:dd
//(double)clock() / CLOCKS_PER_SEC <= 0.95
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f//1,061,109,567
#define PB push_back
#define pii pair<int,int>
#define fer(i,a,n) for (int i=(a);i<=(n);++i)
#define rep(i,n,a) for (int i=(n);i>=(a);--i)
#define fi first
#define se second
#define this_is_fictitious_love ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const ll mod = 1e9+7;
//-------------------------------------------
//void addedge(int u,int v,int w)
//{
//  edges[++cnt]={v,w,head[u]};//v,w,ne
//  head[u]=cnt;
//}
#define OJ
int dp[5005],a[5005],n;
void dfs(int i)
{
    if(i>n)return;
    fer(j,1,i-1)
    {
        if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
    }
    dfs(i+1);
}
signed main()
{
    this_is_fictitious_love
#ifndef OJ
    freopen("file.in", "r", stdin);
    freopen("file.out", "w", stdout);
#endif
    cin>>n;
    fer(i,1,n)
        cin>>a[i];
    fer(i,1,n)dp[i]=1;
    dfs(1);
    fer(i,2,n)dp[i]=max(dp[i],dp[i-1]);//最大的不一定是以最后一个数字结尾的序列
    cout<<dp[n];
}

by Daniel_yao @ 2022-10-08 17:05:47

@fictitious_love 知晓了，谢谢！

by anonymous_letter @ 2022-10-08 18:35:03

@yzy001633 不谢