NYOJ 10 skiing(好题)
2024-08-31 16:31:11
skiing
时间限制:3000 ms | 内存限制:65535 KB
难度:5
- 描述
- Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 516 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更长。事实上,这是最长的一条。
- 输入
- 第一行表示有几组测试数据,输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
后面是下一组数据; - 输出
- 输出最长区域的长度。
- 样例输入
-
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
很好的题-DFS+DP(LIS),看了网上的代码,很牛的感觉,直接用vis数组来保存搜索的结果,和以前hdu一个叫prime path的题很像。
这题我想到了搜索和动态规划,但是没想到用vis数组保存搜索结果(递归实现动态规划也没写过,好菜啊~其实仔细想想不就是二叉树的深度算法吗??求解最长
的单调递增序列。。我还以为可以用LIS算法)
看来经验还是不够啊,加强练习!import java.util.Scanner; public class skiing {
static int n, m; // 行,列
static int[][] vis;
static int[][] map;
static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
static int max;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tcase = sc.nextInt();
while (tcase-- > 0) {
n = sc.nextInt();
m = sc.nextInt();
vis = new int[n][m];
map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
vis[i][j] = 1;
}
}
int ans = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
DFS(i, j);
if(vis[i][j]>ans){
ans=vis[i][j];
}
}
}
System.out.println(ans);
}
} private static int DFS(int x, int y) {
if (vis[x][y] > 1)
return vis[x][y]; // 已经搜索过了,直接返回,剪枝
for (int i = 0; i < 4; i++) { //单调递增递归求解,好神奇的说
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx<0||nextx>=n||nexty<0||nexty>=m) continue;
if(map[x][y]<map[nextx][nexty]){
max = DFS(nextx,nexty); //递归搜索下一层,这样用动态规划好少见
vis[x][y]=vis[x][y]>=max+1?vis[x][y]:max+1; //
}
}
return vis[x][y];
} }
最新文章
- android .apk安装时遇到NSTALL_FAILED_CONTAINER_ERROR错误
- ssh整合,导入structs包后报错 getAnnotation(AnnotatedElement ae,Class<;T>; annotatetype)找不到
- nyoj163_Phone List_字典树
- Logdump使用指引
- 分布式监控系统Zabbix-3.0.3-完整安装记录(6)-微信报警部署
- 字符串数组元素排列与组合的Java递归实现
- 配置webstorm使用supervisor时出现 /usr/bin/env: node: 没有那个文件或目录 解决方法
- CloudStack的VO在调用setRemoved方法抛异常的原因
- Windows 10 (or 8)Chrome 观看视频发生flash不能加载,即";could&#39;t load plugins";原因之一
- Burp Suite Walkthrough(英文版)
- Ubuntu12.04 配置Java开发环境:JDK1.7+Eclipse+Tomcat7.0
- gen_grant_exec.sql
- Django中的From和ModelForm
- 【手记】解决VS发布asp.net项目报错“该项目中不存在目标GatherAllFilesToPublish”及后续问题
- Codeforces Round #406 (Div. 1) A. Berzerk 记忆化搜索
- CSS实现禁止文字选中
- iOS 自己封装的网络请求,json解析的类
- mysql数据库分库分表(Sharding)
- UI设计如何做好排版?你可以学习一下格式塔原理
- 单点登录(一)-----理论-----单点登录SSO的介绍和CAS+选型
热门文章
- Educational Codeforces Round 6 A
- middle中间件
- mpvue开发小记
- Java注释@interface的用法【转】 --好文章 很好理解
- jquery禁用按钮
- 【Android】完善Android学习(四:API 3.1)
- git设置免密码登录
- 【poj2464】树状数组
- 20151024_001_C#基础知识(静态与非静态的区别,值类型和引用类型,堆和栈的区别,字符串的不可变性,命名空间)
- 浅谈Trigger(SimpleTrigger&;CronTrigger)