蒟蒻求dalao解答

P1434 [SHOI2002] 滑雪

6954717a @ 2019-02-16 08:55:06

Code1：

include<cstdio>

#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int mp[15520][5520],f[5520][5520],r,c,ans;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int dfs(int x,int y)
{
    if(f[x][y]!=1) 
    return f[x][y];
    int maxx=0;
    for(int i=0;i<=3;i++)
    if(x>0&&y>0&&x<=r&&y<=c&&mp[x][y]>mp[x+dx[i]][y+dy[i]])
    maxx=max(maxx,dfs(x+dx[i],y+dy[i])+1);
    f[x][y]=max(f[x][y],maxx);
    return f[x][y];
}
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        scanf("%d",&mp[i][j]);
        f[i][j]=1;
    }           
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    ans=max(ans,dfs(i,j));
    printf("%d",ans);
    return 0;
}

Code2:

include<cstdio>

    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int mp[15520][5520],f[5520][5520],r,c,ans;
    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};
    int dfs(int x,int y)
    {
        if(f[x][y]!=1) 
        return f[x][y];
        int maxx=0;
        for(int i=0;i<=3;i++)
        if(x>0&&y>0&&x<=r&&y<=c&&mp[x][y]>mp[x+dx[i]][y+dy[i]])
        maxx=max(maxx,dfs(x+dx[i],y+dy[i])+1);
        f[x][y]=max(f[x][y],maxx);
        return f[x][y];
    }

int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        scanf("%d",&mp[i][j]);
        f[i][j]=1;
    }           
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    ans=max(ans,dfs(i,j));
    printf("%d",ans);
    return 0;
}

by encore @ 2019-02-16 08:56:55

。。。然后呢

by 6954717a @ 2019-02-16 08:57:21

区别就是maxx定义在全局变量和只是定义在dfs里的变量；然而为什么定义在全局变量里的代码所得的结果是错的呢？求助qwq

错的代码：

include<cstdio>

#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int mp[15520][5520],f[5520][5520],r,c,ans,maxx;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int dfs(int x,int y)
{
    if(f[x][y]!=1) 
    return f[x][y];
    maxx=0;
    for(int i=0;i<=3;i++)
    if(x>0&&y>0&&x<=r&&y<=c&&mp[x][y]>mp[x+dx[i]][y+dy[i]])
    maxx=max(maxx,dfs(x+dx[i],y+dy[i])+1);
    f[x][y]=max(f[x][y],maxx);
    return f[x][y];
}
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        scanf("%d",&mp[i][j]);
        f[i][j]=1;
    }           
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    ans=max(ans,dfs(i,j));
    printf("%d",ans);
    return 0;
}

by 6954717a @ 2019-02-16 08:58:37

@encore 就是那个maxx全局变量和定义在dfs里的区别qwq

by 6954717a @ 2019-02-16 09:00:58

求助qwq

by encore @ 2019-02-16 09:01:48

@6954717a 定义成全局变量的话你递归到下一层的时候会把上一次的maxx给覆盖掉啊

by 6954717a @ 2019-02-16 09:06:46

@encore THANKS!dalao 帮助很大！