2 shunfurh shunfurh 于 2017.01.12 22:28 提问

Up and Down

Description

This problem is based on a children's game, Chutes and Ladders, where players take turns jumping a number of steps along a path. If they land on the base of a ladder, they rise to the top of the ladder in the same turn. If they land at the top of a chute, they slide down to the bottom in the same turn. The idea is to get to the final step on the path. In the children's game the number of steps to move in a turn is determined randomly, so the game requires no decisions. In the version here, Up and Down, players get to choose the number of steps to jump forward in each turn. Both figures above show spaces numbered from 0 to 28, with several chutes and ladders. They show two different possible sequences of moves, assuming jumps of 1, 2 or 3 are allowed. Each jump is illustrated starting at a gray dot and ending at an arrowhead, jumping 1-3 places ahead, sometimes ending there, and sometimes shifting up a ladder or down a chute. The players in Figures 1 and 2 finish in 5 and 4 turns respectively. Figure 2 demonstrates the minimum number of turns for this path configuration and a maximum jump of 3.
It gets harder a figure out the best path if there are more chutes and ladders and many more spaces along the path! Be careful of your algorithm, given the large limit on the number of spaces specified below.
Input

The input will consist of one to twenty data sets, followed by a line containing only 0.
The first line of a dataset contains blank separated integers w s p, where w is the number of the winning space, 3 ≤ w ≤ 1,000,000,000, s is the maximum number of spaces to jump in each turn, 2 ≤ s ≤ 6, and p is the total number of chutes and ladders, 1 ≤ p ≤ 40.
The remaining lines of the data set consist of pairs of integers bi ei, for i = 1, 2, ... p. Each bi ei pair is the beginning space and ending space for a chute or ladder, so a turn with a jump to bi actually ends at ei. All the integers are positive and less than w, and none of these 2p numbers appears more than once. Following the rules of the game, it is possible to eventually reach space w, starting from space 0, for each dataset. The numbers bi are in increasing order. Numbers in these lines are separated by either a single blank or a newline.
Output

There is one line of output for each data set, containing only the minimum number of turns it takes to start at space 0 and end at space w, with the jump in each turn chosen as a positive integer no larger than s.
The first sample input data set corresponds to the configuration in the Figures.
Sample Input

28 3 5
2 18 5 13 12 6
17 25 20 15
50 6 1
9 45
0
Sample Output

4
3

2个回答

caozhy
caozhy   Ds   Rxr 2017.01.18 23:52
已采纳
qq_16877261
qq_16877261   2017.01.13 15:54

who are you ? and where are you?

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
信号量,和内核中函数up,down!
信号量的原理就是一个整数的增减,up=加1,down = 减1;当这个值>=1时它就是属于资源释放状态,此时使用down能获得,如果down获得。 其实信号量不是互斥的,linux内核说定义互斥信号量,只是说你把它初始化为1或者0,然后通过配对使用up down来保证。 up的函数就是加1,down的函数就是减1. 例子: DECLARE_MUTEX(regs_mutex);
linux同步机制之信号量down 和up
三、信号量(semaphore)    Linux内核的信号量在概念和原理上和用户态的System V的IPC机制信号量是相同的,不过他绝不可能在内核之外使用,因此他和System V的IPC机制信号量毫不相干。    信号量在创建时需要设置一个初始值,表示同时能有几个任务能访问该信号量保护的共享资源,初始值为1就变成互斥锁(Mutex),即同时只能有一个任务能访问信号量保护的共享资源。
信号量机制中的DOWN操作与UP操作详解
DOWN操作:linux内核中,对信号量的DOWN操作有如下几种: void down(struct semaphore *sem); //不可中断 int down_interruptible(struct semaphore *sem);//可中断 int down_killable(struct semaphore *sem);//睡眠的进程可以因为受到致命信号而被唤醒,中断获取信号量
端口的UP与down
记住: 1.交换机的接口默认的状态是:UP 2.路由器的接口的默认的状态是:DOWN ,所以要记得,用 no  shut down 命令打开。
关于端口协议Up down的一点理解
在处理网络障碍的时候,经常需要查看端口的状态、端口所配协议的状态,使用一些常用的工具里投入ping等命令进行测试。然后大家有没有发现,路由器或者三层交换机针对于广域网的端口的查看和以太网的端口查看包括ping等有很大区别,在此将自己的理解概述如下: 1.       端口状态 端口状态是属于物理层的连接,只要端口能收到相匹配的物理信号(电信号或光信号),端口就能up。广域网的端口和以太网的端口
Extjs4 中up()和down()的用法
Extjs4.x中,每个组件都新增加了两个方法up()和down()方法。这两个方法都是用来获取组件的,下面我们来看下up()方法和down()方法的官方解释。 Extjs4.x中,新增加了两个方法up()和down()方法。这两个方法都是用来获取组件的,下面我们来看下官方解释。 up( String selector, [Number/Mixed maxDepth] ) : Ex
临界资源 互斥访问 内核中的up和down函数
信号量(semaphore)是用于保护临界区的一种常用方法。只有得到信号量的进程才能执行临界区代码,而没有得到信号量的进程进入休眠等待状态。 Linux系统中与信号量相关的操作主要有如下4种。 1 定义信号量 下面代码定义名为sem的信号量。 struct semaphore sem; struct semaohore结构体在内核中定义如下: 在/include/linux/semap
linux网卡linux_up和link_down事件.
有的网卡该事件是采用延迟工作队列轮询, 逻辑在driver/net/phy/phy.c中.
Linux系统网络设备启动和禁止“ifconfig eth0 up/down”命令的跟踪
前面文章讲了Linux系统的ethtool框架的一些东西,是从用户空间可以直观认识到的地方入手。同样,本文从Linux系统绝大部分人都熟悉的“ifconfig eth0 up”命令来跟踪一下此命令在内核中的发生了什么事情。由于ifconfig启动(up)和禁止(down)网络设备很相似,就放到一起讲了。
top down和bottom up
    top down就是top down    bottom up就是bottom up    什么时候该用哪种方法, 要搞清楚。 本来想细写, 但发现今天写了不少东西, 就不细写了。     约下次见面再聊。...