洛谷 P1434 [SHOI2002] 滑雪 完整题解

一、题目查看

P1434 [SHOI2002] 滑雪 - 洛谷

二、解题思路

本题需要使用记忆化搜索，把第x个点开始最多能走几步记录在dp[x]中，循环递归，记录，并找出最大的dp[i]。

三、题解

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

int n, m, mp[105][105], dp[105][105];
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

int dfs(int x, int y, int st);


int main() {
memset(dp, 0, sizeof (dp));
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
}
}
int mx = -1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (dp[i][j] == 0) {
mx = max(mx, dfs(i, j, 0));
}
}
}
cout << mx << endl;
return 0;
}


int dfs(int x, int y, int st) {
if (dp[x][y]) {
return dp[x][y];
}
dp[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx, ny;
nx = x + dir[i][0];
ny = y + dir[i][1];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
if (mp[x][y] > mp[nx][ny]) {
dp[x][y] = max(dp[x][y], dfs(nx, ny, st + 1) + 1);
}
}
}
return dp[x][y];
}

四、测试结果

原文地址：https://blog.csdn.net/applelin2012/article/details/143650831

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！