蒟蒻の问

imfkwk @ 2021-01-30 00:23:07

#include <bits/stdc++.h>
using namespace std;

int h[101][101];
int r, c;
int f[101][101];
int ans;

int fx[] = {0, 1, 0, -1};
int fy[] = {1, 0, -1, 0};

int dfs(int x, int y) {
    if (f[x][y]) return f[x][y];

    int re = 1;

    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i];
        int ty = y + fy[i];
        if (tx > r || tx < 1 || ty > c || ty < 1) continue;
        if (h[tx][ty] > h[x][y]) continue;

        re = max(re, dfs(tx, ty) + 1);
    }

    f[x][y] = re;
    ans = max(ans, re);

    return re;
}

int main(void) {
    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
    scanf("%d", &h[i][j]);

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (!f[i][j]) {
                dfs(i, j);
            }
        }
    }

    printf("%d", ans);

    return 0;
}

by imfkwk @ 2021-01-30 00:39:01

问题已经找出。题目中并没有说没有平坡，而平坡在滑行过程中是不可行的。根据我的代码：

if (h[tx][ty] > h[x][y]) continue;

搜搜到平坡的时候会左右横跳，导致爆内存

by imfkwk @ 2021-01-30 01:06:02

然后，我写了个DP（貌似是的），第十个点WA了

#include <bits/stdc++.h>
using namespace std;

struct xyh{
    int x;
    int y;
    int he;
}d[10001];
int num;

int r, c;
int f[101][101];
int h[101][101];

bool cmp(xyh a, xyh b) {
    return a.he > b.he;
}

int fx[] = {1, 0, -1, 0};
int fy[] = {0, 1, 0, -1};

int ans;

int main(void) {
    scanf("%d%d", &r, &c);

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            scanf("%d", &h[i][j]);
            ++num;
            d[num].x = i;
            d[num].y = j;
            d[num].he = h[i][j];
        }
    }

    sort(d + 1, d + r * c + 2, cmp);

    for (int i = 1; i <= r * c; i++) {
        int nx = d[i].x;
        int ny = d[i].y;
        f[nx][ny] = 1;

        for (int j = 0; j < 4; j++) {
            int tx = nx + fx[j];
            int ty = ny + fy[j];
            if (tx > 0 && tx <= r && ty > 0 && ty <= c && h[tx][ty] > h[nx][ny]) {
                f[nx][ny] = max(f[nx][ny], f[tx][ty] + 1);
            }
        }
    }

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            ans = max(ans, f[i][j]);
        }
    }

    printf("%d", ans);
}

输出是0，我也不知道为什么。有hack吗？

by imfkwk @ 2021-01-30 01:13:21

将

sort(d + 1, d + r * c + 2, cmp);

改为

sort(d + 1, d + r * c + 1, cmp);

之后过了。也就是说我先前多排序的时候多排了一个进去。为什么这个多排的会导致输出为0呢？

by Acfboy @ 2021-01-30 07:04:45

sort 把后面一个地址的值排进来了？

by imfkwk @ 2021-01-30 10:24:31

@Acfboy 但是后面一个地址的值不应该是0吗（那也不影响啊