滑雪

先看题目：https://ac.nowcoder.com/acm/problem/105685
题目描述：
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。任选一点作为起点，问最长滑雪区域的长度。
解题思路：
动态规划入门题，结合此题回顾一下动态规划的一般步骤。
first ，首先结合原问题和子问题确定状态(我是谁，我在哪)
题目在求什么?要求出这个值，我们需要知道什么?什么是影响答案的因素?
(一维描述不完就二维，二维描述不完就三维四维)
这道题状态是显然要描述位置的，定义dp[i][j]为人从坐标（i,j）出发可以最长滑多远。
second ， 确定转移方程(我从哪里来，我到哪里去)
检查参数是否足够，分情况：(最后一次操作，取不取，怎么样取，前一项是什么？)
初始边界是什么。还有要注意无后效性，比如说求A要求B，求B要求C，求C要求A，这就不符合无后效性了。
这道题，从起点，人可以向四个方向中高度小于h的坐标走，故状态转移方程
dp[i][j] = max{dp[i+dir][j+dir]} (h[i+dir][j+dir] < h[i][j])
third ， 确定编程实现方式
递推 or 记忆化搜索
这道题的话递推不太方便，可以使用记忆化搜索。

代码：

#include<bits/stdc++.h>
using namespace std;
int r, c;
int h[10010][10010];
int dp[10010][10010];
int vis[10010][10010];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int dfs(int x, int y)
{
    if(vis[x][y]) return dp[x][y];
    vis[x][y]=1;
    for(int k = 0; k < 4; k++) {
        int dx = x+dir[k][0];
        int dy = y+dir[k][1];
        if(dx < 0 || dx >= r || dy < 0 || dy >= c) continue;
        if(h[dx][dy] >= h[x][y]) continue;
        dp[x][y] = max(dp[x][y], dfs(dx, dy)+1);
    }
    return dp[x][y];
}
int main()
{
    scanf("%d%d",&r,&c);
    for(int i = 0; i < r; i++)
    for(int j = 0; j < c; j++) {
        scanf("%d",&h[i][j]);
        dp[i][j] = 1;
    }
    int ans = 0;
    for(int i = 0; i < r; i++)
    for(int j = 0; j < c; j++) {
        ans = max(ans, dfs(i, j));
    }
    printf("%d\n", ans);
}