信息学奥赛一本通 1280：【例9.24】滑雪 | OpenJudge NOI 2.6 90:滑雪 | 洛谷 P1434 [SHOI2002] 滑雪

【题目链接】

ybt 1280：【例9.24】滑雪
OpenJudge NOI 2.6 90:滑雪
洛谷 P1434 [SHOI2002] 滑雪

【题目考点】

1. 动态规划

2. 记忆化递归

【解题思路】

1. 状态定义

集合：所有的路线
限制：从某位置出发的路线
属性：路线长度
条件：最长
统计量：路线长度
状态定义：dp[i][j]：从(i,j)出发的所有路线中，长度最长的路线的长度。

2. 状态转移方程

记第(i,j)位置的高度为a[i][j]。
集合：从(i,j)出发的所有路线
分割集合：根据下一步可以到达的位置分割集合。
下一步可以到达的位置有：(i-1,j), (i+1,j), (i,j-1), (i,j+1)。只要该位置的高度低于当前(i,j)位置的高度，就可以到达这里。

• 如果a[i-1][j] < a[i][j]，那么下一步可以到(i-1,j)。从(i,j)出发的最长路线长度，为从(i-1,j)出发的最长路线长度再加1，即dp[i][j] = dp[i-1][j] + 1。
• 如果a[i+1][j] < a[i][j]，那么下一步可以到(i+1,j)。从(i,j)出发的最长路线长度，为从(i+1,j)出发的最长路线长度再加1，即dp[i][j] = dp[i+1][j] + 1。
• 如果a[i][j-1] < a[i][j]，那么下一步可以到(i,j-1)。从(i,j)出发的最长路线长度，为从(i,j-1)出发的最长路线长度再加1，即dp[i][j] = dp[i][j-1] + 1。
• 如果a[i][j+1] < a[i][j]，那么下一步可以到(i,j+1)。从(i,j)出发的最长路线长度，为从(i,j+1)出发的最长路线长度再加1，即dp[i][j] = dp[i][j+1] + 1。
• 以上四种情况求最大值。

由于在求(i,j)时，其上下左右四个位置的状态：dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]并不能确定都已经求出来了。因此可以通过记忆化递归的方法来求解状态。
设函数dfs(i, j)，作用为求解状态dp[i][j]。如果dp[i][j]已经求出来了（值大于0），那么直接返回dp[i][j]。否则通过上述状态转移方程递归求解。

遍历所有的位置，求出从每个位置出发的路线的最长长度，求它们中的最大值，即为该问题的结果。

【题解代码】

解法1：动态规划 记忆化递归

#include<bits/stdc++.h>
using namespace std;
#define N 105
int dp[N][N], a[N][N], mx, r, c;//dp[i][j]:从(i,j)出发的最长路线的长度 
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};//方向数组 
int dfs(int sx, int sy)//求dp[sx][sy] 
{
    
    if(dp[sx][sy] > 0)//如果路径长度大于0，则已经求出过dp[sx][sy]，直接返回该值。 
        return dp[sx][sy];
    int route = 0;//从(sx,sy)周围位置出发能得到的最大路线数 
    for(int i = 0; i < 4; ++i)
    {
    
        int x = sx + dir[i][0], y = sy + dir[i][1];
        if(x >= 1 && x <= r && y >= 1 && y <= c && a[x][y] > a[sx][sy])//如果 
            route = max(route, dfs(x, y));
    }
    return dp[sx][sy] = route+1;
}
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)
            mx = max(mx, dfs(i, j));
    cout << mx;
    return 0;
}