aojiaoluolisaiban @ 2024-03-13 20:53:23
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int ii, jj;
cin >> ii >> jj;
int a[105][105];
int dp[105][105]; // 用于记录每个点的最长滑坡长度
for (int i = 0; i < ii; i++) {
for (int j = 0; j < jj; j++) {
cin >> a[i][j];
dp[i][j] = 1; // 初始化为1,因为每个点本身就构成长度为1的滑坡
}
}
int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组
int maxLen = 1; // 记录最大滑坡长度
for (int i = 0; i < ii; i++) {
for (int j = 0; j < jj; j++) {
for (int k = 0; k < 4; k++) {
int x = i + fx[k][0];
int y = j + fx[k][1];
if (x >= 0 && x < ii && y >= 0 && y < jj && a[x][y] < a[i][j]) {
dp[i][j] = max(dp[i][j], dp[x][y] + 1); // 更新当前点的最长滑坡长度
}
}
maxLen = max(maxLen, dp[i][j]); // 更新最大滑坡长度
}
}
cout << maxLen << endl;
return 0;
}
究竟是为什么捏??
by Composite_Function @ 2024-03-13 20:58:47
因为 @aojiaoluolisaiban 这是因为你的搜索顺序是错误的。你会发现当你在计算时 dp[i][j]
不会使用 dp[i + 1][j]
和 dp[i][j + 1]
来计算答案。
建议:将原题改成记忆化搜索。
by aojiaoluolisaiban @ 2024-03-14 20:05:10
@Composite_Function 感谢!