HUST team contest #E A Mountain Road||poj 3846 (dp)-白红宇

HUST team contest #E A Mountain Road||poj 3846 (dp)

阅读量：4654 次

发布时间：2019-06-09

本文共 4560 字，大约阅读时间需要 15 分钟。

Mountain Road

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 310		Accepted: 111

Description

In the Franconian Switzerland, there is a narrow mountain road. With only a single lane, this is a bottleneck for two-way traffic. Your job is to schedule incoming cars at both ends so that the last car leaves the road as early as possible.

Each car is specified by three values: the direction in which it is going, the arrival time at the corresponding beginning of the road, and the driving time this car needs to get through, provided it is not slowed down by other cars in front. Cars cannot overtake each other on the mountain road, and reordering cars in the queues at the ends of the road is not allowed.

For safety reasons, two successive cars going in the same direction may not pass any point of the road within less than 10 seconds. This ensures that the second car will not crash into the first car if the latter brakes hard. However, if another car passes in the other direction in between, it will be clear that the road is empty, so in this case, this rule does not apply.

Input

The first line of the input consists of a single integer c (1 <= c <= 200), the number of test cases.

Then follow the test cases, each beginning with a single line consisting of an integer n (1 <= n <= 200), the number of cars you are to consider in this test case. The remainder of each test case consists of n lines, one line per car, starting with a single upper case letter ("A" or "B"), giving the direction in which the car is going. Then follow, on the same line, two integers t (0 <= t <= 100 000) and d (1 <= d <= 100 000), giving the arrival time at the beginning of the road and the minimum travel time, respectively, both in seconds.

Within a test case, the cars are given in order of increasing arrival time, and no two cars will arrive at the same time.

Output

For each test case, print a single line consisting of the point in time (in seconds) the last car leaves the road when the cars are scheduled optimally.

Sample Input

24A 0 60B 19 10B 80 20A 85 1004A 0 100B 50 100A 100 1A 170 100

Sample Output

Source

比赛的时候以为是贪心...

想了好久.

不过最后没敢写,因为没办法证明正确性,只是直觉==

最后剩下的时间给队友改另一道题了..

果然明智...

蠢的人的直觉真心不靠谱..

这题是dp

我们可以把车按照方向的不同分为A车和B车

dp[i][j][0..1]表示已经经过了a方向的i辆车,经过了b方向的j辆车,并且最后一辆车是a/b方向的情况的离开道路的时间.

似乎问题不大.

然后就一直wa...

wa到怀疑人生好么!!!

最后发现

问题出在!

dp数组初始化赋值成正无穷的时候,溢出啦!

然后我搜了下,发现0x7fffffff果然不是什么好东西!

以后正无穷用0x3f3f3f3f

这东西>1E9,相加不超过int

而且最重要的是,如果定义 inf = 0x3f3f3f3f

0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))

不要使用0x7fffffff!

1 /*************************************************************************  2     > File Name: code/2015summer/0821/E.cpp  3     > Author: 111qqz  4     > Email: rkz2013@126.com   5     > Created Time: 2015年08月21日 星期五 01时28分23秒  6  ************************************************************************/  7   8 #include
      
         9 #include
       
         10 #include
        
          11 #include
         
           12 #include
          
            13 #include
           
             14 #include
            
              15 #include
              16 #include
              
                17 #include
               
                 18 #include
                
                  19 #include
                 
                   20 #define y0 abc111qqz 21 #define y1 hust111qqz 22 #define yn hez111qqz 23 #define j1 cute111qqz 24 #define tm crazy111qqz 25 #define lr dying111qqz 26 using namespace std; 27 #define REP(i, n) for (int i=0;i
                  
                   >q[i].dir>>q[i].beg>>q[i].t; 48 } 49 for ( int i = 0 ; i < n ; i ++){ 50 if (q[i].dir=='A'){ 51 cntA++; 52 a[cntA].beg = q[i].beg; 53 a[cntA].t = q[i].t; 54 } 55 else{ 56 cntB++; 57 b[cntB].beg = q[i].beg; 58 b[cntB].t = q[i].t; 59 60 } 61 } 62 for ( int i = 0 ; i <= cntA ; i ++){ 63 for ( int j = 0 ; j <= cntB ; j++){ 64 dp[i][j][0]=dp[i][j][1]=inf/2; //正无穷溢出了....调了三个小时..妈蛋 65 } 66 } 67 dp[0][0][0]=dp[0][0][1]=0; 68 } 69 70 void solve(){ 71 int l,r; 72 l = r = 0 ; 73 for ( int i = 0 ; i<= cntA ; i++){ 74 for ( int j = 0 ; j <= cntB ; j++){ 75 l = dp[i][j][1]-10; 76 r = dp[i][j][1]-10; 77 for ( int k = i+1 ; k<=cntA ; k++){ 78 l = max(l+10,a[k].beg); 79 r = max(r+10,l+a[k].t); 80 dp[k][j][0] = min (r,dp[k][j][0]); 81 } 82 l = dp[i][j][0]-10; 83 r = dp[i][j][0]-10; 84 for ( int k = j+1 ; k<=cntB ; k++){ 85 l = max(l+10,b[k].beg); 86 r = max(r+10,l+b[k].t); 87 dp[i][k][1] = min (r,dp[i][k][1]); 88 } 89 } 90 } 91 } 92 int main(){ 93 94 int T; 95 cin>>T; 96 while (T--){ 97 init(); 98 solve(); 99 int ans = 0 ;100 ans = min (dp[cntA][cntB][0],dp[cntA][cntB][1]);101 // printf("%d\n",ans);102 cout<
                   
                    <

View Code

转载于:https://www.cnblogs.com/111qqz/p/4746698.html

你可能感兴趣的文章