Informatics Olympiad all in one 1280: [example 9.24] skiing | openjudge noi 2.690: skiing | Luogu p1434 [show2002] skiing

【 Topic link 】

ybt 1280：【 example 9.24】 skiing
OpenJudge NOI 2.6 90: skiing
Luogu P1434 [SHOI2002] skiing

【 Topic test site 】

1. Dynamic programming

2. Memory recursion

【 Their thinking 】

1. State definition

aggregate ： All the routes
Limit ： A route from a certain position
attribute ： Route length
Conditions ： The longest
statistic ： Route length
State definition ：dp[i][j]： from (i,j) Of all the routes to go , The length of the longest route .

2. State transition equation

Note No (i,j) The height of the position is a[i][j].
aggregate ： from (i,j) All the routes of departure
Split set ： Divide the set according to the position that can be reached in the next step .
The next steps are ：(i-1,j), (i+1,j), (i,j-1), (i,j+1). As long as the height of this position is lower than the current (i,j) The height of the position , You can get here .

• If a[i-1][j] < a[i][j], Then the next step is (i-1,j). from (i,j) The length of the longest route of departure , For from (i-1,j) The length of the longest route of departure plus 1, namely dp[i][j] = dp[i-1][j] + 1.
• If a[i+1][j] < a[i][j], Then the next step is (i+1,j). from (i,j) The length of the longest route of departure , For from (i+1,j) The length of the longest route of departure plus 1, namely dp[i][j] = dp[i+1][j] + 1.
• If a[i][j-1] < a[i][j], Then the next step is (i,j-1). from (i,j) The length of the longest route of departure , For from (i,j-1) The length of the longest route of departure plus 1, namely dp[i][j] = dp[i][j-1] + 1.
• If a[i][j+1] < a[i][j], Then the next step is (i,j+1). from (i,j) The length of the longest route of departure , For from (i,j+1) The length of the longest route of departure plus 1, namely dp[i][j] = dp[i][j+1] + 1.
• Find the maximum value in the above four cases .

Because I'm asking (i,j) when , The state of its four positions up, down, left and right ：dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1] I'm not sure it's all worked out . Therefore, the state can be solved by memory recursive method .
Let's set the function dfs(i, j), The function is to solve the state dp[i][j]. If dp[i][j] It has been worked out （ Greater than 0）, Then go straight back dp[i][j]. Otherwise, the above state transition equation is recursively solved .

Traverse all positions , Find the longest length of the route starting from each position , Find the maximum of them , This is the result of the problem .

【 Solution code 】

solution 1： Dynamic programming Memory recursion

#include<bits/stdc++.h>
using namespace std;
#define N 105
int dp[N][N], a[N][N], mx, r, c;//dp[i][j]: from (i,j) The length of the longest route of departure  
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};// Direction array  
int dfs(int sx, int sy)// seek dp[sx][sy] 
{
    
    if(dp[sx][sy] > 0)// If the path length is greater than 0, Has been found dp[sx][sy], Returns the value directly . 
        return dp[sx][sy];
    int route = 0;// from (sx,sy) The maximum number of routes that can be obtained from the surrounding position  
    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])// If  
            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;
}