【面试笔试算法】Problem 1 : DP滑雪问题--网易互联网算法实习生2017笔试题
2024-10-19 01:27:48
Description
Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是 为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由 一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
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。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
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
Sample Output
25
Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是 为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由 一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
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。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
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
Sample Output
25
// SkiProgram.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <stdio.h> using namespace std; //全局变量 int map[100][100] = { -1 };//输入数组 int path[100][100] = { -1 };//记录每个点的最长路径 int maxResult = -1; //记录最大值 int rows, cols; //行列数 int dps(int i, int j) { int& result = path[i][j]; //读取该点的路径 if (result > 0)//递归结束标志,如果已经计算过就返回该点的最长路径 { return result; } result = 1; int temp = 0; if (i + 1 < rows && map[i][j] > map[i + 1][j])//如果右边的值比自己小,则右移 { temp = dps(i + 1, j) + 1;//递归 if (temp > result)//如果路径比result大,则赋值给result { result = temp; } } if (i - 1 >= 0 && map[i][j] > map[i - 1][j])//如果左边的值比自己小,则左移 { temp = dps(i - 1, j) + 1;//同上 if (temp > result) { result = temp; } } if (j + 1 < cols && map[i][j] > map[i][j+1])//如果上面的值比自己小,则上移 { temp = dps(i, j+1) + 1;//同上 if (temp > result) { result = temp; } } if (j - 1 >= 0 && map[i][j] > map[i][j-1])//如果下边的值比自己小,则下移 { temp = dps(i, j-1) + 1;//同上 if (temp > result) { result = temp; } } if (result > maxResult)//求取最大路径长度 { maxResult = result; } return result; } int main() { while (cin >> rows >> cols) { for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols;++j) { cin >> map[i][j]; } } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { dps(i, j); } } cout << maxResult << endl; } return 0; }
最新文章
- idea的修改文件变颜色
- zigbee学习之路(三):按键的控制
- TabCtrl的基本用法
- source命令
- pku3659 Cell Phone Network
- JS实现的一个验证码,可以在前端验证后在提交action
- js移除最后一个字符,js替换字符串的连接符号,js移除最后一个分隔符号
- 定制rpm包---Yum环境搭建
- Linux(CentOS6.5)下修改Nginx初始化配置
- HTML知识点总结之<;a>;标签
- Eclipse中的所有快捷键列表
- combobox数据绑定
- vscode 搭建go开发环境的13个插件的安装
- linux 普通用户批量创建账户与密码
- 新版的 selenium已经放弃PhantomJS改用Chorme headless
- Fetch的使用; Yarn命令集; NVM的管理;VueCLi3的使用;
- 多线程处理慢sql查询小笔记~
- 使用Java创建Excel,并添加内容
- 浅谈count(*)、count(1)、count(列名)
- Codeforces Round #361 (Div. 2) D - Friends and Subsequences
热门文章
- 大数据基础知识问答----spark篇,大数据生态圈
- Cassandra Secondary Index 介绍
- Web Service进阶(三)HTTP-GET, HTTP-POST and SOAP的比较
- BeanUtils Exception 之 FastHashMap
- SELinux策略语言--客体类别和许可
- Android图片setBackgroundResource和setImageResource的区别
- C语言中switch case语句可变参实现方法(case 参数 空格...空格 参数 :)
- Java并发框架——AQS之阻塞与唤醒
- Servlet3.0注解@WebInitParam和@WebServlet
- 保证service存活