空中之虎 @ 2023-02-21 17:58:48
事情是这样的，我在dp的题单里找到了这道题，理所当然的想用dp来做，感觉这道题的递推式还是蛮好想的： dp[i][j] = max(dp[i][j], dp[i + x[k]][j + y[k]])
然而这样写有个问题：我没办法找到整个数组中地势高的数，也就是当我dp到地势高的点时，它周围地势地的点可能还未更新，因而答案肯定是错的。（不然我就发题解去了hhh）
此时我突发奇想，如果能循环足够多的次数，让dp完成足够多次的更新，会不会获得正确的答案？于是有了以下代码：
#include <bits/stdc++.h>
const int x[] = {0, 1, -1, 0, 0};
const int y[] = {0, 0, 0, 1, -1};
int map[110][110];
int dp[110][110];
int ans = -1;
int main()
{
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf ("%d", &map[i][j]);
dp[i][j] = 1;
}
}
for (int b = 1; b <= 100; b++){
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= 4; k++)
{
if (map[i][j] > map[i + x[k]][j + y[k]])
dp[i][j] = std::max(dp[i][j], dp[i + x[k]][j + y[k]] + 1);
}
ans = std::max(ans, dp[i][j]);
}
}
}
std::cout << ans;
return 0;
}通过代码风格也能很明显的看出来哪重循环是新加的吧hhh
试着交了一下结果发现90分……只有第二个点WA掉了……（话说有没有大佬愿意帮我改一改让我A掉发题解区hhh）
（dp好难学，根本学不会嘤嘤嘤）
by Usada_Pekora @ 2023-02-21 18:00:46
bellman-ford。
by vzcx_host @ 2023-02-21 18:02:23
这种思路我以前用过，循环 n*m 次能过
by Usada_Pekora @ 2023-02-21 18:06:29
@空中之虎
#include <bits/stdc++.h>
const int x[] = {0, 1, -1, 0, 0};
const int y[] = {0, 0, 0, 1, -1};
int map[110][110];
int dp[110][110];
int ans = -1;
int main() {
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf ("%d", &map[i][j]);
dp[i][j] = 1;
}
}
for (int b = 1; b <= n * m; b++) {
bool upd = false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= 4; k++) {
if (map[i][j] > map[i + x[k]][j + y[k]])
if (dp[i + x[k]][j + y[k]] + 1 > dp[i][j])
dp[i][j] = dp[i + x[k]][j + y[k]] + 1, upd = true;
}
ans = std::max(ans, dp[i][j]);
}
}
if (!upd)
break;
}
std::cout << ans;
return 0;
}
by Usada_Pekora @ 2023-02-21 18:09:29
其实不算什么很新的思路，建图然后跑最长路。
by 空中之虎 @ 2023-02-21 18:44:50
@Industrial_banana 我也试了循环n * m次，结果TLE了hhh
by 空中之虎 @ 2023-02-21 18:45:23
@Usada_Pekora 大概看明白了 谢谢大佬！