记忆化搜索40ptsRE求助！

一个句号 @ 2023-08-01 16:32:14

#include<iostream>
#include<cstring>
using namespace std;
//暴力？
int n;
int a[5005]; 
int maxans=0;

int mem[5005][5005];
void dfs(int num,int pos,int ans){
    if(pos==n){
        maxans=max(maxans,ans);
        return ;
    }
    mem[num][pos]=max(mem[num][pos],ans); 
    for(int i=pos+1;i<=n;i++){
        if(a[i]>num){
            if(mem[a[i]][i]!=-1) continue;//只求一次，是不是没必要？            
            dfs(a[i],i,ans+1);
        }
    }
}

signed main(){
    memset(mem,-1,sizeof(mem));
    cin>>n;
    for(int i=1;i<=n;i++)   
        cin>>a[i];
    dfs(a[1],1,1);
    cout<<maxans;
    return 0;
} 

by 一个句号 @ 2023-08-01 17:04:23

写了个离散解决了，但是WA了！！！！！

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//暴力？
int n;
int a[5005],t[5005],b[5005]; 
int maxans=0;

int mem[5010][5010];
void dfs(int num,int pos,int ans){
    if(pos==n){
        maxans=max(maxans,ans);
        return ;
    }
    mem[num][pos]=max(mem[num][pos],ans); 
    for(int i=pos+1;i<=n;i++){
        if(a[i]>num){
            if(mem[a[i]][i]!=-1) continue;          
            dfs(a[i],i,ans+1);
        }
    }
}

signed main(){
    memset(mem,-1,sizeof(mem));
    cin>>n;
    for(int i=1;i<=n;i++)   
        cin>>b[i],t[i]=b[i];
    stable_sort(t+1,t+n+1);
    int len=unique(t+1,t+n+1)-t-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(t+1,t+len+1,b[i])-t;
    }
    dfs(0,0,0);
    cout<<maxans;
    return 0;
} 

by GY程袁浩 @ 2023-08-01 17:10:03

mem是二维数组是不是没必要啊，只保留pos就可以了吧。

#include<iostream>
#include<cstring>
using namespace std;
//暴力？
int n;
int a[5005]; 
int maxans=0;

int mem[5005];
void dfs(int num,int pos,int ans){
    if(pos==n){
        maxans=max(maxans,ans);
        return ;
    }
    mem[pos]=max(mem[pos],ans); 
    for(int i=pos+1;i<=n;i++){
        if(a[i]>num){
            if(mem[i]!=-1) continue;//只求一次，是不是没必要？            
            dfs(a[i],i,ans+1);
        }
    }
}

signed main(){
    memset(mem,-1,sizeof(mem));
    cin>>n;
    for(int i=1;i<=n;i++)   
        cin>>a[i];
    dfs(a[1],1,1);
    cout<<maxans;
    return 0;
}