玄学的MLE

P1434 [SHOI2002] 滑雪

suxiaozhou @ 2023-11-03 20:53:10

以下是我有疑惑的代码

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

int high[110][110], mem[110][110], n, m, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}, ans = 0;
int dfs(int x, int y) {
    if (x > n || x < 1 || y > m || y < 1) {
        return 0;
    }
    if (mem[x][y] != -1) {
        return mem[x][y];
    }
    int ans_dfs = 0;
    for (int i = 0; i < 4; i++) {
        if (high[x + dx[i]][y + dy[i]] > high[x][y]) {
            continue;
        }
        ans_dfs = max(dfs(x + dx[i], y + dy[i]), ans_dfs);
    }
    mem[x][y] = ++ans_dfs;
    return ans_dfs;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> high[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(dfs(i, j), ans);
        }
    }
    cout << ans << endl;
    return 0;
}

以上代码得分50pts,5个点MLE...

然而当我尝试将:

if (high[x + dx[i]][y + dy[i]] > high[x][y]) {

改动成:

if (high[x + dx[i]][y + dy[i]] >= high[x][y]) {

马上就AC了...

有神犇可以解释为什么会这样吗?谢谢!


by dry_ @ 2023-11-11 16:59:14

注意:是下坡(单调下降)


by suxiaozhou @ 2023-11-12 18:35:06

@tjtdrxxz 您可能不理解我想问的事情,我的意思是为什么单调下降不会爆MLE,而写成单调不增就会爆了MLE呢?


by dry_ @ 2023-11-12 21:22:38

单调不增会增加很多额外的情况 例: 3 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 正确的输出是1,但改成单调不下降后就废了


by sxhy @ 2024-03-08 17:54:24

@tjtdrxxz 感谢?


|