P1434 [SHOI2002]滑雪

原题链接

P1434 [SHOI2002]滑雪

解题思路

刚开始我以为题目要求解的最大长度是,从那个点滑下来的最大高度差。后来一想,不太对啊。其实要求的是从某一个点滑下的可以经过的最多的点的个数。可以把它看作是地图,就是要找最长的步数。
dfs(i,j)指的是从i,j这个点出发能够得到的最大步数,很显然,这个步数就等于它前后左右四个方向的最大个数+1。
其中,需要记忆化搜索,将dfs(i,j)的值记录到数组dp中,如果已经计算过该值,则可以直接返回。

代码

#include <bits/stdc++.h>
using namespace std;
int a[110][110];
int dp[110][110];//dp[i][j]从i,j位置下落可以达到的最大长度
int r,c;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int ans = 0;

//从(x,y)点搜索下去,可以得到的最大长度 
int dfs(int x,int y){
    if(dp[x][y]) return dp[x][y];//已经存在了,直接返回
    dp[x][y] = 1;//如从边界处的1滑下,滑坡的长度为1.也就是本身也算一次步数 
    for(int i=0;i<4;i++){
        int xx = dx[i]+x;
        int yy = dy[i]+y;
        if(xx>0&&yy>0&&xx<=r&&yy<=c){//符合条件 
            if(a[x][y]>a[xx][yy]){//只能往低的地方去 
                dfs(xx,yy);
                dp[x][y] = max(dp[x][y],dp[xx][yy]+1);
            } 
        }
    } 
    return dp[x][y];
} 
int main(){

    scanf("%d%d",&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++){
            ans = max(ans,dfs(i,j));
        }
    }   
    cout<<ans<<'\n'; 
    return 0;
} 
Tags:

Add a Comment

邮箱地址不会被公开。