题目理解问题,关于谷底s[i][j]的值

P1434 [SHOI2002] 滑雪

xijue_08 @ 2020-10-28 09:51:57

按照题解的思路,谷底对应的值是1。 为什么谷底对应的值不是0,也就是滑不了呢?

#include<iostream>
#include<vector>
using namespace std;
/*
例如测试用例
4 4
10 9 8 7
10 5 8 8
10 9 9 9
10 9 9 9
输出
0 0 0 0 0 0
0 4 3 2 1 0
0 1 0 1 2 0
0 2 1 2 3 0
0 2 1 1 1 0
0 0 0 0 0 0
*/

static int longest = 0;
static int R = 0;
static int C = 0;
static int m[102][102];
static int dp[102][102];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void ski(int x, int y) {
    if(dp[x][y]) return;
    int xx, yy;
    for(int i = 0; i < 4; i++) {
        xx = x + dx[i];
        yy = y + dy[i];
        if(xx >= 0 && yy >= 0 && xx <= R+1 && yy <=C+1 && m[x][y] > m[xx][yy]) {
            ski(xx, yy);
            dp[x][y] = max(dp[x][y], dp[xx][yy]+1);
        }
    }
}

int main () {
    cin>>R>>C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin>>m[i][j];
        }
    }

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            ski(i, j);
            longest = max(longest, dp[i][j]);
        }
    }

    /*cout<<endl;
    for (int i = 0; i <= R+1; i++) {
        for (int j = 0; j <= C+1; j++) {
            cout<<dp[i][j]<<' ';
        }
        cout<<endl;
    }*/

    cout<<longest;
    return 0;
}

by watermonster @ 2020-10-28 11:04:03


by xijue_08 @ 2020-10-28 12:39:59

@LSG_watermonster 是的,我这里的dp就是别人题解中的s,表示此点可以滑行的最大距离


by watermonster @ 2020-10-28 13:04:43

@xijue_08 谷底自己也算长度啊所以是1


by xijue_08 @ 2020-10-28 13:49:03

@LSG_watermonster 哦哦,是这样的么,我可能理解错了,我是觉得例如中间的谷底(就是代码中例子的5位置)四周都没有办法滑,所以是0来着。。。但是这么理解不对。 把基础值设成1就过了


|