【HDU - 5477】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≤501≤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,RiLi,Ri, which represents the interval [Li,Ri][Li,Ri] is swamp. 
1≤n≤100,1≤L≤105,1≤A≤10,1≤B≤10，1≤Li<Ri≤L1≤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+1Ri<Li+1 for each i (1≤i<n1≤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

题目大意：

Mr.D 带着他的女朋友出去旅行，资金缺乏，就骑着自行车出发了！路途中会遇到沼泽地和平坦路。每在沼泽地骑行一米，Mr.D能量值减少a,每在平坦大路上骑行一米就恢复能量值b。为了能成功到达目的地，在出发前至少需补充多少能量。

解题报告：

跟之前做过的一个机器人的差不多，数形结合一下，横轴是到原点的距离，纵轴是能量变化，先假设原点的能量是0，最后输出图像的最低点就可以了。

AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<cctype> using namespace std; typedef long long ll; const int maxn=1e4+5; int n,L,a,b; int l[maxn],r[maxn]; int main() {int t,i,j,k,cnt=0,nf;ll sum,ans;cin>>t;r[0]=0;for(;t;t--){scanf("%d%d%d%d",&n,&a,&b,&L); sum=ans=nf=0;if(nf) continue;for(i=1;i<=n;i++){scanf("%d%d",l+i,r+i);sum+=1LL*(l[i]-r[i-1])*b;sum-=1LL*(r[i]-l[i])*a;if(sum<0) {ans+=-sum;sum=0;}}printf("Case #%d: %lld\n",++cnt,ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的【HDU - 5477】A Sweet Journey（思维，水题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。