一、题目查看

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];
}

四、测试结果