首页 > ACM题库 > HDU-杭电 > hdu 2703 The Bridges of San Mochti-动态规划-[解题报告]C++
2014
02-14

hdu 2703 The Bridges of San Mochti-动态规划-[解题报告]C++

The Bridges of San Mochti

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

-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

样例输出:

17
75
190
145
162

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2703

题意:有n条通道首尾相连,每个通道有一个容量p和一个通过时间sec,表示最多一次能一起进p个人,需要sec的时间通过。现在有m个人在第一条通道的开始处,他们按照策略通过n条通道。策略有2点要遵守,1是每个通道同一时间只能进一组人,2是只要通道为空并且通道口有人,通道口的人必须立刻进入通道(显然这不一定是最佳策略)。

现在就按要求模拟题意,最后问m个人都通过的总用时。

mark:一开始觉得是个纯阅读题,再后来发现写起来有的地方也挺难想的。数据规模较小,直接暴搞(总用时最大才780s)。

代码:

# include <stdio.h>
 # include <string.h>
 
 
 int n ;
 int dp[25][2010] ;
 int p[25], sec[25] ;
 
 
 int min(int a, int b){return a<b?a:b;}
 int max(int a, int b){return a>b?a:b;}
 
 
 int gao()
 {
     int ans = 0, t = 0 ;
     int i, j ;
     for (i = 0 ; i < n ; i++)
     {
         for (j = 0 ; ; j++)
         {
             if (j != 0) dp[i][j] += dp[i][j-1] ;
             if (j > ans && dp[i][j] == 0) break ;
             if (t != 0) t-- ;
             else if (dp[i][j] != 0)
             {
                 dp[i+1][j+sec[i]] += min(dp[i][j], p[i]) ;
                 dp[i][j] -= min(dp[i][j], p[i]) ;
                 t = sec[i]-1 ;
                 ans = max(ans, j+sec[i]) ;
             }
         }
     }
     return ans ;
 }
 
 
 int main ()
 {
     int m, i ;
     while (1)
     {
         scanf ("%d%d", &n, &m) ;
         if (n == 0 && m == 0) break ;
         n = -n ;
         for (i = 0 ; i < n ; i++)
             scanf ("%d%d", &p[i], &sec[i]) ;
             
         memset (dp, 0, sizeof(dp)) ;
         dp[0][0] = m ;
         
         printf ("%d\n", gao()) ;
     }
     return 0 ;
 }

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/05/04/2482582.html


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience