90分求助,WA了第6个点

courtesan @ 2019-08-16 16:32:23

#include<bits/stdc++.h>
#define peak 100005
using namespace std;
int slope[105][105];
int dp[105][105];//代表每个点的最长距离 
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
int dfs(int i,int j)
{
    if(dp[i][j]!=0) return dp[i][j];
    else if(i==0||j==0||i==n+1||j==m+1) return 0;   
    int ans=0;
    for(int p=0;p<4;p++)
    if(slope[i][j]>slope[i+dir[p][0]][j+dir[p][1]])
    ans=max(ans,dfs(i+dir[p][0],j+dir[p][1])+1);
    dp[i][j]=ans;
    return ans;
}

int main()
{

cin>>n>>m;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
slope[i][j]=peak;

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>slope[i][j];

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(slope[i][j]<slope[i-1][j]&&slope[i][j]<slope[i+1][j]&&slope[i][j]<slope[i][j-1]&&slope[i][j]<slope[i][j+1])
dp[i][j]=1;//找出所有的谷底 

int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans=max(ans,dfs(i,j));

cout<<ans;
} 

by courtesan @ 2019-08-16 16:33:25

话说这个题90分的WA的都是不同的点惹，我看到的就有WA1、2、4、9 90分的惹

by courtesan @ 2019-08-16 20:46:25

有没有大佬可以帮一下蒟蒻啊

by courtesan @ 2019-08-16 21:28:47

镇楼最后是j<=m，改过来还是WA了那个点惹

by Surpersolo @ 2019-08-20 09:38:53

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110][110],f[110][110]= {},t,maxn,sum;
int dx[]= {1,-1,0,0};
int dy[]= {0,0,1,-1};
int search(int x,int y) {
    if(f[x][y]>0)
        return f[x][y];
    t=1;
    for(int i=0; i<=3; i++) {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]>a[x][y]) {
         sum=search(nx,ny)+1;
            if(sum>t)
                t=sum;
        }
    }
    f[x][y]=t;
    return t;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>a[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            t=search(i,j);
            f[i][j]=t;
            if(f[i][j]>maxn)
                maxn=f[i][j];
        }
    cout<<maxn;
    return 0;
}

by Surpersolo @ 2019-08-20 09:39:21

@courtesan 你还是看下我的吧，我的这个好理解 AC的用记忆化搜索

by 厂里sgh @ 2020-12-24 09:40:05

在搜索方向的时候小于改大于就好了 slope[i][j]<slope[i+dir[p][0]][j+dir[p][1]]就是这样

by Damaxiaoshitou @ 2021-08-18 12:05:42

wa 6

测试

2 2

1 1

1 1