题解 | #滑雪#

解题思路：

• 关键点，是找到起始的位置，在输入地图的同时，把点(i,j)的高度和其坐标保存下来$point{s}_{hight(i,j)}points\_\{hight(i,j)\}$,再将points按照hight排序。那么拍完序以后的内容就是我们要处理点的顺序。
• 接下来只要对于points里面的每一个点取出来以后判断上下左右是否在图内，如果在，则记录下上下左右四个点连续的最大值，然后和自己比较取最大值即可$dp[i][j]=max(max(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1]),1)dp[i][j]\; =\; max(max(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1]),1)$
• 最后遍历dp表，取出最大值输出即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    vector<vector<int>> mp(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m));
    vector<pair<int,pair<int, int>>> points;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin>>mp[i][j];
            points.push_back(make_pair(mp[i][j],make_pair(i,j)));//取得所有的点
        }
    }
    sort(points.begin(), points.end());//对点排序
    while(points.size()){//依次处理每个点计算上下左右
        int i, j;
        pair<int,pair<int,int>> current_point = points.back();
        points.pop_back();
        i = current_point.second.first;
        j = current_point.second.second;
        int hight = current_point.first;
        int mx = 1;
        if(i-1>=0 && i-1< n) {
            if(mp[i][j] < mp[i-1][j]) mx = max(dp[i-1][j]+1,mx);
        }
        if(i+1>=0 && i+1 < n){
            if(mp[i][j] < mp[i+1][j]) mx = max(dp[i+1][j]+1, mx);
        }
        if(j-1>=0 && j-1 < m){
            if(mp[i][j] < mp[i][j-1]) mx = max(dp[i][j-1]+1, mx);
        }
        if(j+1>=0 && j+1 < m){
            if(mp[i][j] < mp[i][j+1]) mx = max(dp[i][j+1]+1, mx);
        }
        dp[i][j] = max(dp[i][j], mx);
    }
    int mx_ans = 0;
    for(int i = 0; i < n; ++i){//取出表中最大值
        for(int j = 0; j < m; ++j){
            mx_ans = max(dp[i][j],mx_ans);
        }
    }
    cout<<mx_ans<<endl;
    return 0;
}