sv优雅 2022-07-11 17:21 采纳率: 50%
浏览 47
已结题

C爱滑雪 不会啊 希望思路+解析

问题遇到的现象和发生背景

今天在做题的时候,遇到一道搜索题.

问题相关代码,请勿粘贴截图

描述
C teacher喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而
且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。C想知道在一个区域中最长的滑
坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可行的
滑坡为24 17 16 1(从24开始,在1结束)。当然25 24 23 3 2 1更长。事实上,这是
最长的一条。
输入
输入的第一行为表示区域的二维数组的行数R和列数C(1≤R,C≤100)。下面是R行,每行有C个数,代
表高度(两个数字之间用1个空格间隔)。
输出
输出区域中最长滑坡的长度。
输入样例 1
输出样例 1
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
25

运行结果及报错内容

运行后我超时了

我想要达到的结果

希望有人作详细的注释解析,我在网上看了没懂!

  • 写回答

2条回答 默认 最新

  • 关注
    
    #include <bits/stdc++.h>
    
    using namespace std ;
    
    const int N = 1010 ;
    int n , m , res ;
    int g[N][N] , f[N][N] ;
    int dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0 , 1 , 0 , -1} ;
    
    int dp (int x , int y)
    {
        int & v = f[x][y] ;
        if (v != -1) return v ;
        else v = 1 ;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i] , yy = y + dy[i] ;
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[x][y] > g[xx][yy])
            {
                v = max (v , dp (xx , yy) + 1) ;
            }
        }
        return v ;
    }
    
    int main ()
    {
    
    
        cin >> n >> m ;
        memset (f , -1 , sizeof (f)) ;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)  cin >> g[i][j] ;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++) res = max (res , dp (i , j)) ;
        }
        cout << res << endl ;
    
    
        return 0 ;
    }
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 7月20日
  • 已采纳回答 7月12日
  • 创建了问题 7月11日

悬赏问题

  • ¥15 关于#linux#的问题(输入输出错误):出现这个界面接着我重新装系统,又让修电脑的师傅帮我扫描硬盘(没有问题)用着用着又卡死(相关搜索:固态硬盘)
  • ¥15 cv::resize不同线程时间不同
  • ¥15 web课程,怎么做啊😭没好好听课 根本不知道怎么下手
  • ¥15 做一个关于单片机的比较难的代码,然后搞一个PPT进行解释
  • ¥15 python提取.csv文件中的链接会经常出现爬取失败
  • ¥15 数据结构中的数组地址问题
  • ¥15 maya的mel里,怎样先选择模型A,然后利用mel脚本自动选择有相同名字的模型B呢。
  • ¥15 Python题,根本不会啊
  • ¥15 会会信号与系统和python的来
  • ¥15 关于#python#的问题