## 题目描述 Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子： ```markup 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 ``` 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24-17-16-1$（从 $24$ 开始，在 $1$ 结束）。当然 $25$－$24$－$23$－$\\ldots$－$3$－$2$－$1$ 更长。事实上，这是最长的一条。 ## 输入格式输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。 ## 输出格式输出区域中最长滑坡的长度。 ## 样例 #1 ### 样例输入 #1 ```markup 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 ``` ### 样例输出 #1 ```markup 25 ``` ## 提示对于 $100\\%$ 的数据，$1\\leq R,C\\leq 100$。 ## 题解 ```cpp #include using namespace std; int r, c, ans = -1, a[110][110], maxx[110][110]; int ss[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int dfs(int x, int y) { if (maxx[x][y]) return maxx[x][y]; maxx[x][y] = 1; for (int i = 0; i < 4; i++) { int tx = x + ss[i][0]; int ty = y + ss[i][1]; if (tx < 1 || ty < 1 || tx > r || ty > c) continue; if (a[tx][ty] >= a[x][y]) continue; dfs(tx, ty); maxx[x][y] = max(maxx[x][y], maxx[tx][ty] + 1); } return maxx[x][y]; } int main() { cin >> r >> c; for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) cin >> a[i][j]; } for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) ans = max(ans, dfs(i, j)); } cout << ans; return 0; } ```

记忆化搜索

洛谷P1434 [SHOI2002] 滑雪