记忆化搜索50求助

zzyxl_qaq @ 2023-05-08 21:04:43

#include<bits/stdc++.h>
#define re register
#define ll long long
#define inl inline
ll h[105][105],f[105][105],ans(-1);
inl ll dfs(ll x,ll y){
    if(f[x][y])return f[x][y];
    if(h[x][y]>h[x+1][y])f[x][y]=std::max(dfs(x+1,y)+1,f[x][y]);
    if(h[x][y]>h[x-1][y])f[x][y]=std::max(dfs(x-1,y)+1,f[x][y]);
    if(h[x][y]>h[x][y+1])f[x][y]=std::max(dfs(x,y+1)+1,f[x][y]);
    if(h[x][y]>h[x][y-1])f[x][y]=std::max(dfs(x,y-1)+1,f[x][y]);
    return f[x][y];
}
int main(){
    std::memset(f,0,sizeof(f));
    re ll n,m;
    scanf("%lld %lld",&n,&m);
    for(re ll i(1);i<=n;++i){
        for(re ll j(1);j<=m;++j)scanf("%lld",&h[i][j]);
    }
    for(re ll i(1);i<=n;++i){
        for(re ll j(1);j<=m;++j)ans=std::max(ans,dfs(i,j));
    }
    printf("%lld",ans);
}

by __er @ 2023-05-08 21:09:34

@Slytherin_always 判边界了吗

by zzyxl_qaq @ 2023-05-08 21:18:29

@__er 草，wssb，过了（

by xueruo @ 2023-06-06 17:45:46

@__er

判了边界的记忆化搜索的50分求调

#include<iostream>
#include<climits>
#include<cstdio> 
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define int long long
#define F(i,j,n) for(register int i=j;i<=n;++i)
using namespace std;
int n,m,ans;
const int N=1010;
int a[N][N],book[N][N];
int dx[5]={0,-1,0,1,0};
int dy[5]={0,0,1,0,-1};
inline int dfs(int x,int y){
    if(x<1||x>n||y<1||y>m)return 0;
    if(book[x][y])return book[x][y];
    register int mx=0;
    F(i,1,4){
        if(a[x+dx[i]][y+dy[i]]<a[x][y]){
            mx=max(mx,dfs(x+dx[i],y+dy[i])+1);
        }
    }
    return book[x][y]=mx;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    F(i,1,n){
        F(j,1,m){
            scanf("%lld",&a[i][j]);
        }
    }
    F(i,1,n){
        F(j,1,m){
            ans=max(ans,dfs(i,j));
        }
    }
//  printf("%lld\n",dfs(3,3));
    printf("%lld",ans);
    return 0;
}