2015 ACM/ICPC Asia Regional Shanghai Online-1010-A Sweet Journey

Master Di plans to take his girlfriend for a travel by bike. Their journey, which can be seen as a line segment of length L, is a road of swamps and flats. In the swamp, it 

takes A point strengths per meter for Master Di to ride; In the flats, Master Di will regain B point strengths per meter when riding. Master Di wonders：In the beginning, he needs to prepare how much minimum strengths. (Except riding all the time,Master Di has no other choice) 

Input

In the first line there is an integer t (1≤t≤50 ), indicating the number of test cases.
For each test case:
The first line contains four integers, n, A, B, L.
Next n lines, each line contains two integers: Li,Ri , which represents the interval [Li,Ri] is swamp.
1≤n≤100,1≤L≤105,1≤A≤10,1≤B≤10，1≤Li<Ri≤L .
Make sure intervals are not overlapped which means Ri<Li+1 for each i (1≤i<n ).
Others are all flats except the swamps.

 

Output

For each text case:
Please output “Case #k: answer”(without quotes) one line, where k means the case number counting from 1, and the answer is his minimum strengths in the beginning.

 

 

Sample Input

1

2 2 2 5

1 2

3 4

 

Sample Output

Case #1: 0

题目意思是说一个人在一条由0点到L点的路上骑车，每个整数点上都有沼泽或者公寓，每骑行经过一个公寓点会回复B点能量，每经过一个沼泽点会损失A能量，问你若要骑行完这条路，开始时最少需要多少能量。

Sample Input

1（测试次数）

2（几块沼泽地） 2（A的值） 2（B的值） 5（L的值）

1 2（第一块沼泽区间）

3 4（第二块沼泽区间）

 

Sample Output

Case #1: 0（开始需要的最少能量值）

这道题是一道简单的计算题，假设初始能量点sum为0，只需要把每块沼泽地出现前的能量点与沼泽地消耗的能量相比较，如果能量剩余，则令sum=0；如果能量不够，令sum=e-s+sum；同时每次比较之后把沼泽地消耗能量清零。当时因为忘了清零，居然wa了一发。代码如下：

#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    int jishu=0;
    while(t--)
    {
        jishu++;
        int n,a,b,l;
        scanf("%d %d %d %d",&n,&a,&b,&l);
        int c,d,s=0,e=0,sum=0,m=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&c,&d);
            s=(c-m)*b+s;
            e=(d-c)*a;
            m=d;
            if(s>=e)
            {
                sum=sum;
                s=s-e;
                e=0;
            }
            else
            {
                sum=e-s+sum;
                e=0;
                s=0;
            }
        }
        printf("Case #%d: %d\n",jishu,sum);
    }
    return 0;
}