HDU 5477: A Sweet Journey

A Sweet Journey

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 25 Accepted Submission(s): 12

Problem Description

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

Sample Output

Case #1: 0

最近状态一直不怎么好，想了很多问题都没有想出答案。当然了，我这种状态好了也不会好到哪里去。。。

只能切一切这种菜题了。。。

题意就是一个人去旅行，有沼泽地有平坦地，平坦地可以涨力气，沼泽地耗力气。问如果能顺利到达目的地的话，一开始要准备多少力气。

代码：

#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
#include <string>  
#include <cstring>  
#pragma warning(disable:4996)  
using namespace std;

int dis[100005];

int main()
{
	int test,i,j,n,A,B,L,temp1,temp2,ans;
	scanf("%d",&test);
	for(i=1;i<=test;i++)
	{
		memset(dis,0,sizeof(dis));
		scanf("%d%d%d%d",&n,&A,&B,&L);
		for(j=1;j<=n;j++)
		{
			scanf("%d%d",&temp1,&temp2);
			dis[temp2]=(-1)*(temp2-temp1)*(A+B);
		}
		ans=0;
		for(j=1;j<=L;j++)
		{
			dis[j]=dis[j-1]+dis[j]+B;
			ans=min(ans,dis[j]);
		}
		printf("Case #%d: %d
",i,-1*ans);
	}
	return 0;
}