第二点一直TLE,求大佬指教

逝星DS @ 2018-08-10 10:40:53

#include <iostream>
#include <cstdio>
using namespace std;
int N,M;
int X[101][101];
int maxstep=0;
int sx,sy;
int f[101][101];
int walkx[4]={0,0,1,-1},walky[4]={1,-1,0,0};
void dfs(int step,int x,int y);
void read(int &a)
{
    a=0;int d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;a=a*10+c-48;
    while (c=getchar(),c>='0'&&c<='9') a=a*10+c-48;
    a*=d;
}
int main()  {
    //freopen("1.txt","r",stdin);
    read(N),read(M);
    for(int i=1;i<=N;i++)  {
        for(int j=1;j<=M;j++)  {
            read(X[i][j]);

        }
    }
    for(int i=0;i<=N+1;i++)  {
        for(int j=0;j<=M+1;j++)  {
            f[i][j]=-1;
        }
    }
    for(sx=1;sx<=N;sx++)  {
        for(sy=1;sy<=M;sy++)  {
            dfs(1,sx,sy);
        }
    }
    for(int i=1;i<=N;i++)  {
        for(int j=1;j<=M;j++)  {
            if(f[i][j]>maxstep)  maxstep=f[i][j];
        }
    }
    cout<<maxstep;
    return 0;
}
void dfs(int step,int x,int y)  {
    bool flag=false;
    int nx,ny;
    for(int i=0;i<=3;i++)  {
        nx=x+walkx[i];
        ny=y+walky[i];
        if(nx>=1 && nx<=N && ny>=1 && ny<=M && X[nx][ny]<X[x][y])  {
            flag=true;
            if(f[nx][ny]!=-1 && step+f[nx][ny]>f[sx][sy])  {
                f[sx][sy]=step+f[nx][ny];
            }
            else  dfs(step+1,nx,ny);
        }
    }
    if(flag==false)  {
        f[sx][sy]=max(step,f[sx][sy]);
    } 

    return;
}

by Snowflake_Pink @ 2018-08-12 17:51:50

#include <iostream>
#include <cmath>
using namespace std;
int t[201][201],rom[201][201],r,c,big;
int dfs(int x,int y){
    if (x<1||x>r||y<1||y>c)  return rom[x][y];
    if (rom[x][y]!=1) return rom[x][y];
    int m=1;
    if (t[x+1][y]>t[x][y]) m=max(m,dfs(x+1,y)+1);
    if (t[x-1][y]>t[x][y]) m=max(m,dfs(x-1,y)+1);
    if (t[x][y+1]>t[x][y]) m=max(m,dfs(x,y+1)+1);
    if (t[x][y-1]>t[x][y]) m=max(m,dfs(x,y-1)+1);
    return m;
}
int main(){
    cin >>r>>c;
    for (int i=1;i<=r;i++)
        for (int j=1;j<=c;j++){
            rom[i][j]=1;
            cin >>t[i][j];
        }
    for (int i=1;i<=r;i++)
        for (int j=1;j<=c;j++)
            big=max(dfs(i,j),big);
    cout <<big;
    return 0;
}

by Snowflake_Pink @ 2018-08-12 17:52:16

宝宝心里苦啊~

by Snowflake_Pink @ 2018-08-12 18:03:28

我1004ms，感到非常无奈，这是开氧的。 不开氧我1012ms，我真是要哭了

by Estella @ 2018-10-14 23:42:59

这题dfs用int吧，记忆化

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int r,c;
int ans,cnt=1;
int a[205][205];
int b[205][205];
int d[5][2]={{1,0},{0,1},{-1,0},{0,-1}};
int read(){
    int s=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){
        s=s*10+c-48;c=getchar();
    }
    return s;
}
int dfs(int x,int y){
    if(b[x][y]>0)return b[x][y];
    b[x][y]=1;
    for(int i=0;i<4;i++){
        if(x+d[i][0]>=1&&x+d[i][0]<=r&&y+d[i][1]>=1&&y+d[i][1]<=c&&a[x][y]<a[x+d[i][0]][y+d[i][1]]){
            b[x][y]=max(b[x][y],dfs(x+d[i][0],y+d[i][1])+1);
        }
    }
    return b[x][y];
}
int main(){
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            a[i][j]=read();
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ans=max(ans,dfs(i,j));
        }
    }
    printf("%d",ans);
}