一个TLE，新人求助

__nullptr__attr @ 2019-10-29 20:35:56

#include<bits/stdc++.h>
using namespace std;
int r,c,a[110][110],v[110][110],ans=0;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
template<class I>
inline void read(I &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
}
void dfs(int x,int y,int step){
    ans=max(ans,step);
    v[x][y]=1;
    for(int i=0;i<4;++i){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<1||nx>r||ny<1||ny>c) continue;
        if(v[nx][ny]) continue;
        if(a[nx][ny]>=a[x][y]) continue;
        v[nx][ny]=1;
        dfs(nx,ny,step+1);
        v[nx][ny]=0;
    }
    v[x][y]=0;
}
int main(){
    read(r);read(c);
    for(int i=1;i<=r;++i)
     for(int j=1;j<=c;++j)
      read(a[i][j]);
    for(int i=1;i<=r;++i)
     for(int j=1;j<=c;++j)
      dfs(i,j,1);
    cout<<ans<<endl;
    return 0;
}

by ⚡小林孑⚡ @ 2019-10-29 20:41:00

@BSSR 需要用记忆化搜索

by __nullptr__attr @ 2019-10-29 20:42:11

@脱发自动机 QAQ但我其他点都几毫秒过，就这个第二点（一般来说不应该是最后一个点最毒吗）

by ⚡小林孑⚡ @ 2019-10-29 20:43:57

@BSSR 记忆化，我原来也是，加了记忆化1.2s->6ms

by __nullptr__attr @ 2019-10-29 20:44:36

@脱发自动机 记忆化这么厉害吗QwQ，我去学

by ⚡小林孑⚡ @ 2019-10-29 20:46:04

@BSSR 代码：

#include<iostream>
using namespace std;
int c,k;
int dt[900][900];
int mem[900][900];
int ans,the_ans=1; 

int move(int x,int y)
{   
    if (mem[x][y] > 0) return mem[x][y];
    int ans = 1;

    if (dt[x-1][y]<dt[x][y]&&x-1>0) 
    {
       ans = max(ans, move(x-1,y)+1);
    }
    if (dt[x][y-1]<dt[x][y]&&y-1>0) 
    {

       ans = max(ans, move(x,y-1)+1);
    }
    if (dt[x+1][y]<dt[x][y]&&x+1<=c) 
    {

       ans = max(ans, move(x+1,y)+1);
    }
    if (dt[x][y+1]<dt[x][y]&&y+1<=k) {

       ans = max(ans, move(x,y+1)+1);
    }
    mem[x][y] = ans;
    return ans;
}
int main()
{
cin>>c>>k;
for(int i=1;i<=c;i++)
{
    for(int ii=1;ii<=k;ii++)
     {
        cin>>dt[i][ii];
     }
}
int the_ans = 0;
for(int i=1;i<=c;i++)
{
    for(int ii=1;ii<=k;ii++)
    {
        the_ans = max(the_ans, move(i,ii));
    }
}
cout<<the_ans;
return 0;
} 

很久以前写的，丑的很

by __nullptr__attr @ 2019-10-29 20:52:16

@脱发自动机 %%%%%

by cpphzj @ 2019-11-10 14:58:42

if (l[x][y]) return l[x][y];

这个很重要。