滑雪

分析

思路：对于矩阵中的一个点，每次滑动有四种可能（上下左右），那么从当前区域开始滑的最大值为滑往四个方向的最大值+1

dp分析

1. 状态表示 $f[i][j]$:

• 集合：所有从$(i,j)$这个点开始滑动的路径
• 属性：所有路径中的最大值

1. 状态计算 ：为以下四种（合法）情况的最大值

• 滑往上方：$f[i-1][j]+1$
• 滑往下方：$f[i+1][j]+1$
• 滑往左方：$f[i][j-1]+1$
• 滑往右方：$f[i][j+1]+1$

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 305;
int r,c;
int h[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x,int y){
    int tx,ty;
    int res = 1;
    for (int i = 0; i < 4; i ++ ){
        tx = x + dx[i],ty = y + dy[i];
        if(tx >= 1 && tx <= r && ty >= 1 && ty <= c && h[x][y] > h[tx][ty]){
            res = max(res,dp(tx,ty) + 1);
        }
    }
    return res;
}

int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i ++ ){
        for (int j = 1; j <= c; j ++ ){
            cin >> h[i][j];
        }
    }
    int res = 0;
    for (int i = 1; i <= r; i ++ )
        for (int j = 1; j <= c; j ++ )
            res = max(res,dp(i,j));
            
    cout << res;      
    return 0;
}

优化

但是上述代码在评测时会超时，其中的原因是在计算$dp$函数时，其中的很多状态都进行了重复的递归计算，所以可以将状态计算中所算出的每一步状态保存起来，避免重复计算

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 305;
int r,c;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x,int y){
    int tx,ty;
    //记忆化搜索关键
    if(f[x][y]!=-1) return f[x][y];
    f[x][y] = 1;
    for (int i = 0; i < 4; i ++ ){
        tx = x + dx[i],ty = y + dy[i];
        if(tx >= 1 && tx <= r && ty >= 1 && ty <= c && h[x][y] > h[tx][ty]){
            f[x][y] = max(f[x][y],dp(tx,ty) + 1);
        }
    }
    return f[x][y];
}

int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i ++ ){
        for (int j = 1; j <= c; j ++ ){
            cin >> h[i][j];
        }
    }
    memset(f, -1, sizeof f);
    int res = 0;
    for (int i = 1; i <= r; i ++ )
        for (int j = 1; j <= c; j ++ )
            res = max(res,dp(i,j));
            
    cout << res;      
    return 0;
}

Q.E.D.