hdu3440 House Man--单源最短路径&差分约束
发布日期:2021-10-03 20:32:12
浏览次数:1
分类:技术文章
本文共 2464 字,大约阅读时间需要 8 分钟。
原题链接:
一:原题内容
Problem Description
In Fuzhou, there is a crazy super man. He can’t fly, but he could jump from housetop to housetop. Today he plans to use N houses to hone his house hopping skills. He will start at the shortest house and make N-1 jumps, with each jump taking him to a taller house than the one he is jumping from. When finished, he will have been on every house exactly once, traversing them in increasing order of height, and ending up on the tallest house. The man can travel for at most a certain horizontal distance D in a single jump. To make this as much fun as possible, the crazy man want to maximize the distance between the positions of the shortest house and the tallest house. The crazy super man have an ability—move houses. So he is going to move the houses subject to the following constraints: 1. All houses are to be moved along a one-dimensional path. 2. Houses must be moved at integer locations along the path, with no two houses at the same location. 3. Houses must be arranged so their moved ordering from left to right is the same as their ordering in the input. They must NOT be sorted by height, or reordered in any way. They must be kept in their stated order. 4. The super man can only jump so far, so every house must be moved close enough to the next taller house. Specifically, they must be no further than D apart on the ground (the difference in their heights doesn't matter). Given N houses, in a specified order, each with a distinct integer height, help the super man figure out the maximum possible distance they can put between the shortest house and the tallest house, and be able to use the houses for training.
Input
In the first line there is an integer T, indicates the number of test cases.(T<=500) Each test case begins with a line containing two integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤1000000). The next line contains N integer, giving the heights of the N houses, in the order that they should be moved. Within a test case, all heights will be unique.
output
For each test case , output “Case %d: “first where d is the case number counted from one, then output a single integer representing the maximum distance between the shortest and tallest house, subject to the constraints above, or -1 if it is impossible to lay out the houses. Do not print any blank lines between answers.
Sample Input
34 4 20 30 10 40 5 6 20 34 54 10 15 4 2 10 20 16 13
Sample Output
Case 1: 3Case 2: 3Case 3: -1
二:分析理解
三:AC代码
转载地址:https://blog.csdn.net/LaoJiu_/article/details/51043557 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月01日 07时16分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
AndroidStudio安卓原生开发_Android扫描附近指定的蓝牙设备_通过设备名称过滤_计算距离_离扫描设备近的显示的时候放在前面---Android原生开发工作笔记128
2019-04-26
网站制作---网站伪静态的介绍
2019-04-26
微信公众开放平台开发01---微信公众平台介绍,以及开发准备
2019-04-26
微信公众开放平台开发02---微信公众平台PHP接口和java接口对比
2019-04-26
微信公众开放平台开发06---复习一下servlet
2019-04-26
微信公众开放平台开发08---纯java 实现微信开发:编写自定义菜单
2019-04-26
二维码相关---java生成二维码名片,并且自动保存到手机通讯录中...
2019-04-26
ASP.Net学习笔记003--网站和WebApplication的区别
2019-04-26
微信小程序开发学习笔记004--微信小程序语法结构
2019-04-26
微信小程序开发学习笔记005--微信小程序组件详解
2019-04-26
微信小程序开发学习笔记006--微信小程序组件详解02
2019-04-26
微信小程序开发学习笔记007--微信小程序项目01
2019-04-26
MySQL 在控制台插入数据时,中文乱码问题的解决
2019-04-26
微信小程序开发学习笔记008--微信小程序项目02
2019-04-26