求助,80分,第1和第10wa了

P1434 [SHOI2002] 滑雪

DKsniper @ 2023-08-21 08:39:44

#include<cstdio>
#include<cstring>
using namespace std;
int c,r,a[105][105],zc[105][105],fx[8][2]={{0,1},{0,-1},{-1,-1},{-1,0},{-1,1},{1,-1},{1,0},{1,1}},wz[10010][2],h,t,t1,ans=-1;
void dfs(int x,int y)
{
    for(int j=0;j<8;j++)
    {
        int xx=x+fx[j][0],yy=y+fx[j][1];
        if(xx>0 && xx<=r && yy>0 && yy<=c)
        {
            if(a[xx][yy]<a[x][y] && zc[xx][yy]<zc[x][y]+1)
            {
                zc[xx][yy]=zc[x][y]+1;
                dfs(xx,yy);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            zc[i][j]=1;
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            dfs(i,j);
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(zc[i][j]>ans)
            {

                ans=zc[i][j];
            }
        }

    }
    printf("%d",ans);
}

by _Clown__ @ 2023-08-21 08:53:09

我的做法是记搜


by _Clown__ @ 2023-08-21 08:53:52

大致是这样:

int dfs(int x,int y){
    if(dp[x][y])return dp[x][y];
    dp[x][y]=1;
    for(int i=0;i<4;i++){
        int tx=dx[i]+x,ty=dy[i]+y;
        if(tx>0&&ty>0&&tx<=n&&ty<=m&&h[x][y]>h[tx][ty]){
            dfs(tx,ty);
            dp[x][y]=max(dp[x][y],dp[tx][ty]+1);
        }
    }
    return dp[x][y];
}
int main(){   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&h[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,dfs(i,j));

by _Clown__ @ 2023-08-21 08:55:10

@dzxken 您可以加一个记搜


by I_Love_QingYu @ 2023-12-11 21:23:33

哈哈哈哈哈哈,我要笑死,虽然我和你一样的错误,但我还是要笑,题目只能上下左右,不能斜向走


|