讨论讨论玄学代码，数组扩大两次分数提升两次是什么...求助互助！

P1434 [SHOI2002] 滑雪

ACDG @ 2021-05-25 23:36:21

看到有帖子里说是数组小了，萌萌叉叉的我又去看了下R和C的范围就是100呀，无奈抱着玄学之心去试了一下（其实我也认为不会WA一半）。结果调成1000又对了一个就60分！再尝试5100结果太大不行，调小一点4000多就又提高了，80分！刚刚试了试把a数组调成相同的4000结果WA了一般又50分了！

#include<iostream>
#include<algorithm>//有很多算法函数，至少可以用min哦
#include<cstring>//使用memsent需要
using namespace std;
int a[3100][3100] = {};//存储滑雪地图
int dp[4100][4100] = {};//存储记忆搜索
int R, C;
int slove(int i, int j)
{
    if (i < 0 || i >= R || j < 0 || j >= C)return 0;//如果越界就返回0
    if (dp[i][j] != -1)return dp[i][j];
    int q=-1, w=-1, e=-1, r=-1;//定义四个变量
    if(a[i-1][j]<a[i][j])
        q = slove(i - 1, j);
    if (a[i][j-1] < a[i][j])
        w = slove(i , j-1);
    if (a[i][j+1] < a[i][j])
        e = slove(i, j+1);
    if (a[i+1][j] < a[i][j])
        r = slove(i+1, j);
    if ((q + w + e + r) == -4)return dp[i][j] = 0;//如果四边都为-1都不能走，则赋值且返回0
    return dp[i][j] = 1 + max(max(q,w),max(e,r));//否则状态转移
}

int main()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> a[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    int max = 0;
    for (int i = 0; i < R; i++)//枚举状态
    {
        for (int j = 0; j < C; j++)
        {
            int x = slove(i,j);
            if (x > max)max = x;//记录最大值
        }
    }
    cout << max << endl;
    return 0;
}

刚学习动态规划入门，希望大家指教！

by 阿丑 @ 2021-05-26 07:23:38

~~可能是您哪个地方数组越界了~~

by 阿丑 @ 2021-05-26 07:27:23

@ACDG 您在写

if(a[i-1][j]<a[i][j])
    q = slove(i - 1, j);
if (a[i][j-1] < a[i][j])
    w = slove(i , j-1);
if (a[i][j+1] < a[i][j])
    e = slove(i, j+1);
if (a[i+1][j] < a[i][j])
    r = slove(i+1, j);

的时候没有判断 i-1 j-1 是不是小于 0（就是有没有越界），虽然我不知道和数组大小有没有关系 qwq

by ACDG @ 2021-05-26 08:47:26

@阿丑我改了一下稳定在80分了，是有一点问题，谢谢你的指正<(￣︶￣)>。WA在8和10，能不能再帮我看下哇。

#include<iostream>
#include<algorithm>//有很多算法函数，至少可以用min哦
#include<cstring>//使用memsent需要
using namespace std;
int a[110][110] = {};
int dp[110][110] = {};
int R, C;
int slove(int i, int j)
{
    if (i < 0 || i >= R || j < 0 || j >= C)return 0;
    if (dp[i][j] != -1)return dp[i][j];
    int q=-1, w=-1, e=-1, r=-1;
    if(i-1<0)q=0;
    else if(a[i-1][j]<a[i][j])
            q = slove(i - 1, j);
    if(j-1<0)w=0;
    else if (a[i][j-1] < a[i][j])
            w = slove(i , j-1);
    if(j+1>=C)e=0;
    else if (a[i][j+1] < a[i][j])
            e = slove(i, j+1);
    if(i+1>=R)r=0;
    else if (a[i+1][j] < a[i][j])
        r = slove(i+1, j);
    if ((q + w + e + r) == -4)return dp[i][j] = 0;
    return dp[i][j] = 1 + max(max(q,w),max(e,r));
}

int main()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> a[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    int max = 0;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            int x = slove(i,j);
            if (x > max)max = x;
        }
    }
    cout << max << endl;
    return 0;
}

by ACDG @ 2021-05-26 08:48:02

@阿丑确实是，我太不小心了qwq

by 阿丑 @ 2021-05-26 11:41:39

@ACDG

if ((q + w + e + r) == -4)return dp[i][j] = 0;

这里应该返回 1，~~我之前没看出来~~

by ACDG @ 2021-05-26 12:15:28

@阿丑改了一下AC了。想了想，原来不是求滑块之间经过的路，而是经过的滑块数，滑自己也是滑。谢谢你，受教了！