记忆化搜索,#2TLE了,大佬帮忙看看,谢谢

P1434 [SHOI2002] 滑雪

F_Q_chicken @ 2023-01-09 11:58:51

#include<bits/stdc++.h>
#define RC 105
using namespace std;
namespace IO{
    char ibuf[(1<<20)+1],*iS,*iT;
    #if ONLINE_JUDGE
    #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #else
    #define gh() getchar()
    #endif
    inline long long read(){
        char ch=gh();
        long long x=0;
        bool t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
using IO::read;
int xy[5][3]={{0,1},{0,-1},{1,0},{-1,0}};
int r,c,ux[RC][RC],f[RC][RC];
bool b[RC][RC];
int dfs(int i,int j){
    if(b[i][j]==1)
    return f[i][j];
    int k=1;
    f[i][j]=1;
    for(int ko=0;ko<=3;ko++){
        int q=i+xy[ko][0];
        int w=j+xy[ko][1];
        if(ux[i][j]>ux[q][w]&&q>=1&&q<=r&&w>=1&&w<=c)
        {
            f[i][j]=max(dfs(q,w)+1,f[i][j]);
        }
    }
    return f[i][j];
}
int main(){
    r=read();c=read();
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ux[i][j]=read();
        }
    }
    int ans=-1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            int df=dfs(i,j);
            if(ans<df)
            ans=df;
        }
    }
    write(ans);
    return 0;
}

by jason_sun @ 2023-01-09 12:04:48

你记忆化没写对,要加 b[i][j]=1


by jason_sun @ 2023-01-09 12:05:16

@345678910jpk


by F_Q_chicken @ 2023-01-09 17:51:21

@jason_sun 谢谢大佬


|