一、题目查看
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]; }
四、测试结果
