2 shunfurh shunfurh 于 2017.09.05 10:47 提问

The Bridges of San Mochti

Problem Description
You work at a military training facility in the jungles of San Motchi. One of the training exercises is to cross a series of rope bridges set high in the trees. Every bridge has a maximum capacity, which is the number of people that the bridge can support without breaking. The goal is to cross the bridges as quickly as possible, subject to the following tactical requirements:
One unit at a time!
If two or more people can cross a bridge at the same time (because they do not exceed the capacity), they do so as a unit; they walk as close together as possible, and they all take a step at the same time. It is never acceptable to have two different units on the same bridge at the same time, even if they don't exceed the capacity. Having multiple units on a bridge is not tactically sound, and multiple units can cause oscillations in the rope that slow everyone down. This rule applies even if a unit contains only a single person.
Keep moving!
When a bridge is free, as many people as possible begin to cross it as a unit. Note that this strategy doesn't always lead to an optimal overall crossing time (it may be faster for a group to wait for people behind them to catch up so that more people can cross at once). But it is not tactically sound for a
group to wait, because the people they're waiting for might not make it, and then they've not only wasted time but endangered themselves as well.
Periodically the bridges are reconfigured to give the trainees a different challenge. Given a bridge configuration, your job is to calculate the minimum amount of time it would take a group of people to cross all the bridges subject to these requirements.
For example, suppose you have nine people who must cross two bridges: the first has capacity 3 and takes 10 seconds to cross; the second has capacity 4 and takes 60 seconds to cross. The initial state can be represented as (9 0 0), meaning that 9 people are waiting to cross the first bridge, no one is waiting to cross the second
bridge, and no one has crossed the last bridge. At 10 seconds the state is (6 3 0). At 20 seconds the state is (3 3 /3:50/ 0), where /3:50/ means that a unit of three people is crossing the second bridge and has 50 seconds
left. At 30 seconds the state is (0 6 /3:40/ 0); at 70 seconds it's (0 6 3); at 130 seconds it's (0 2 7); and at 190 seconds it's (0 0 9). Thus the total minimum time is 190 seconds.

Input
The input consists of one or more bridge configurations, followed by a line containing two zeros that signals the end of the input. Each bridge configuration begins with a line containing a negative integer –B and a positive integer P, where B is the number of bridges and P is the total number of people that must cross the bridges. Both B and P will be at most 20. (The reason for putting –B in the input file is to make the first line of a configuration stand out from the remaining lines.) Following are B lines, one for each bridge, listed in order from the first bridge that must be crossed to the last. Each bridge is defined by two positive integers C and T, where C is the capacity of the bridge (the maximum number of people the bridge can hold), and T is the time it takes to cross the bridge (in seconds). C will be at most 5, and T will be at most 100. Only one unit, of size at most C, can cross a bridge at a time; the time required is always T, regardless of the size of the unit (since they all move as one). The end of one bridge is always close to the beginning of the next, so the travel time between bridges is zero.

Output
For each bridge configuration, output one line containing the minimum amount of time it will take (in seconds) for all of the people to cross all of the bridges while meeting both tactical requirements.

Sample Input
-1 2
5 17
-1 8
3 25
-2 9
3 10
4 60
-3 10
2 10
3 30
2 15
-4 8
1 8
4 30
2 10
1 12
0 0

Sample Output
17
75
190
145
162

2个回答

caozhy
caozhy   Ds   Rxr 2017.09.07 23:47
已采纳
shen_wei
shen_wei   Ds   Rxr 2017.09.05 15:15
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
HDU 2703 The Bridges of San Mochti
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2701 题意:有N条通路以及M个人,每条通路每次仅能通过w个人,每一组人通过需要花费时间t,且需要满足2个条件        1.每次只能有一组人进入一条通路        2.当通路入口有人且通路为空则必须进入 思路:题目很长……刚开始题目都没有读懂,
POJ2288Islands and Bridges(状态压缩DP,求最大路和走条数)
Islands and Bridges Time Limit: 4000MS   Memory Limit: 65536K Total Submissions: 8845   Accepted: 2296 Description Given a map of islands and bridges that connect these i
Burning Bridges-ZOJ1588(割边求解)
Burning Bridges Time Limit: 5 Seconds Memory Limit: 32768 KB Ferry Kingdom is a nice little country located on N islands that are connected by M bridges. All bridges are very beautiful and are l
BZOJ2095: [Poi2010]Bridges
题目大意:给一张图,每条边有一个a到b的代价,同时还有一个b到a的代价,求一个经过所有边所有点的路径使得路径代价最大值最小 首先知道要二分,这样这张图就变成了一些边固定了方向而另一些边两个方向都可以走,这就是一个经典的混合图欧拉回路问题,直接求解即可 混合图欧拉回路知识点讲解戳→这里 #include #include #include #include #define N
POJ 2288 Islands and Bridges (TSP 状态压缩DP)
Islands and Bridges(POJ 2288) Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 11563 Accepted: 3034 Description Given a map of islands and bridges that connect these islands,...
JZOJ 1769.Islands and Bridges
Description 给定一些岛屿和一些连接岛屿的桥梁,大家都知道汉密尔顿路是访问每个岛屿一次的路线,在我们这个地图中,每个岛屿有个正整数的权值,表示这个岛屿的观赏价值。假设一共有N个岛屿,用Vi表示岛屿Ci的价值,汉密尔顿路C1C2….Cn的价值是以下三部分的总和:   (1)所有岛屿的价值之和;   (2)对于路径中相邻的两个岛屿CiCi+1,把两个岛屿的价值之积加到总价值中;   (3
2095: [Poi2010]Bridges 二分+混合图欧拉回路(网络流)
好厉害的题啊QAQ,并不会做。 最大值最小想到是二分,然后就是一个混合图欧拉回路的问题。混合图欧拉回路问题的解决: 我们首先想到有向图的欧拉回路,需满足的条件是每个点的入度等于出度。那么对于一个混合图来说,可能有的点入度>出度,而有的点入度<出度,对于这种情况,我们可能可以通过改变一条边的方向来使这两个点都满足入度等于出度的条件。 那么我们可以首先给这个图的无向边随便定一个方向
POJ 2288 Islands and Bridges 状态压缩DP
题意:给出n个岛和它们之间联通的m条路径,给出权值的计算方法,求权值最大哈密顿回路的权值和数量。 n<=13. 权值的计算方法为: 1.经过的所有点的权值之和; 2.经过的连续的两个点的权值的乘积; 3.能够组成三角形的三个点的权值的乘积。 根据岛是否走过最多有(1<<13)种状态。 dp[s][i][j] = max{ dp[s][i][j] , dp[s’][j][k] + tmp
bzoj2095: [Poi2010]Bridges 二分+最大流
想当年第一次看到这个题是在**p的一套模拟题里?然后当时想过二分也想过最大流。然后就是没有想到一块,最后知道做法后就不了了之了。#include #include #include #include #include #include using namespace std; #define INF 0x3fffffff #define maxn 8000 typedef long l
POJ 2288 Islands and Bridges(状压dp)
Language: Default Islands and Bridges Time Limit: 4000MS   Memory Limit: 65536K Total Submissions: 9312   Accepted: 2424 Description Given a map of islands and bridge