90分，第二个点TLE了

pencil @ 2021-08-04 09:22:32

#include<bits/stdc++.h>
using namespace std;
int a[110][110],dx[5]= {0,0,0,1,-1},dy[5]= {0,-1,1,0,0},n,m;
bool f[110][110];
int s(int at,int b,int h,int p) {
    if(at>n||b>m||f[at][b]||at<1||b<1)
        return 0;   
        int ff=0;
    if(a[at][b]<h||p)
        ff++;
    else
        return 0;
        int i,big=-1,a1,b1;
    f[at][b]=1;
    for(i=1; i<=4; i++) {
        a1=at+dx[i];
        b1=b+dy[i];
//      f[a1][b1]=1;
        big=max(big,s(a1,b1,a[at][b],0));
//      f[a1][b1]=0;
    }
    f[at][b]=0;
    return big+ff;
}
int main() {
    int i,js,i2,maxx=-1,j;
    cin>>n>>m;
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            //  f[i][j]=1;
            maxx=max(maxx,s(i,j,a[i][j],1));
            //  f[i][j]=0;
        }
    } 
    cout<<maxx;
    return 0;
}

by Fan_Tuan @ 2021-08-04 09:26:54

记搜？

by pencil @ 2021-08-04 09:31:28

@Fan_Tuan 我尝试了，但是掉到了四十分QWQ

by Fan_Tuan @ 2021-08-04 09:46:51

#include<bits/stdc++.h>
using namespace std;
int a[110][110],dx[5]= {0,0,0,1,-1},dy[5]= {0,-1,1,0,0},n,m,j[110][110];
bool f[110][110];
int s(int at,int b,int h,int p) {

    if(at>n||b>m||f[at][b]||at<1||b<1)
        return 0;   
        int ff=0;
    if(a[at][b]<h||p)
        ff++;
    else
        return 0;
        if(j[at][b]>0)
        return j[at][b];
        int i,big=-1,a1,b1;
    f[at][b]=1;
    for(i=1; i<=4; i++) {
        a1=at+dx[i];
        b1=b+dy[i];
//      f[a1][b1]=1;
        big=max(big,s(a1,b1,a[at][b],0));
//      f[a1][b1]=0;
    }
    f[at][b]=0;
    j[at][b]=big+ff;
    return big+ff;
}
int main() {
    int i,js,i2,maxx=-1;
    cin>>n>>m;
    for(i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
    for(i=1; i<=n; i++) {
        for(int j2=1; j2<=m; j2++) {
            //  f[i][j]=1;
            int op=s(i,j2,a[i][j2],1);
        //  j[i][j2]=op;
            maxx=max(maxx,op);
            //  f[i][j]=0;
        }
    } 
    cout<<maxx;
    return 0;
}

你原来记搜代码改了改

by Fan_Tuan @ 2021-08-04 09:47:41

j[at][b]=big+ff;

你在这里进行记忆化的时候没加上ff

by Fan_Tuan @ 2021-08-04 09:48:02

@pencil

by pencil @ 2021-08-04 10:10:13

@Fan_Tuan Orz谢谢大佬

by mfXR @ 2021-08-04 14:06:41

@Fan_Tuan