给定一个 的矩阵,矩阵中的数字表示滑雪场各个区域的高度,你可以选择从任意一个区域出发,并滑向任意一个周边的高度严格更低的区域(周边的定义是上下左右相邻的区域)。请问整个滑雪场中最长的滑道有多长?(滑道的定义是从一个点出发的一条高度递减的路线)。
(本题和矩阵最长递增路径类似,该题是当年NOIP的一道经典题)
数据范围: ,矩阵中的数字满足
第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数,表示矩阵的各个元素大小。
输出最长递减路线。
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
25
从25出发,每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1
#include <bits/stdc++.h> using namespace std; int dfs(vector<vector<int>> &arr, int n, int m, int i, int j, int pre, vector<vector<int>> &dp) { if (i < 0 || i >= n || j < 0 || j >=m || arr[i][j] >= pre) return 0; if (dp[i][j] != -1) return dp[i][j]; dp[i][j] = 1; dp[i][j] = max(dp[i][j], dfs(arr, n, m, i - 1, j, arr[i][j], dp) + 1); dp[i][j] = max(dp[i][j], dfs(arr, n, m, i + 1, j, arr[i][j], dp) + 1); dp[i][j] = max(dp[i][j], dfs(arr, n, m, i, j - 1, arr[i][j], dp) + 1); dp[i][j] = max(dp[i][j], dfs(arr, n, m, i, j + 1, arr[i][j], dp) + 1); return dp[i][j]; } int main() { int n, m, res = 0; cin >> n >> m; vector<vector<int>> arr(n, vector<int>(m, 0)), dp(n, vector<int>(m, -1)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) cin >> arr[i][j]; } // 时间复杂度O(N^2),空间复杂度O(N) for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { res = max(res, dfs(arr, n, m, i, j, INT_MAX, dp)); } } cout << res; return 0; }
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 105, M = 105; int grid[N][M], dp[N][M], n, m; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int dfs(int x, int y, int prev) { if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] >= prev) return 0; if(dp[x][y] != -1) return dp[x][y]; int path = 1; for(int i = 0; i < 4; i++) { path = max(path, 1 + dfs(x + dx[i], y + dy[i], grid[x][y])); } dp[x][y] = path; return path; } int main() { scanf("%d%d", &n, &m); memset(dp, -1, sizeof dp); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%d", &grid[i][j]); int ans = 1; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) ans = max(ans, dfs(i, j, 1001)); printf("%d", ans); return 0; }