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 感谢?