题目描述
Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For their purposes (and yours), the mountain can be represented as a long straight trail of length LL meters (1 ≤ L ≤ 106). Farmer John will hike the trail at a constant travel rate of rF seconds per meter (1 ≤ rF ≤ 106). Since he is working on his stamina, he will not take any rest stops along the way.
Bessie, however, is allowed to take rest stops, where she might find some tasty grass. Of course, she cannot stop just anywhere! There are N rest stops along the trail (1 ≤ N ≤ 105); the i-th stop is xi meters from the start of the trail (0 < xi < L) and has a tastiness value ci (1 ≤ ci ≤ 106). If Bessie rests at stop i for t seconds, she receives ci⋅t tastiness units.
When not at a rest stop, Bessie will be hiking at a fixed travel rate of rB seconds per meter (1 ≤ rB ≤ 106). Since Bessie is young and fit, rB is strictly less than rF.
Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!
Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.
输入
The first line of input contains four integers: L, N, rF, and rB. The next N lines describe the rest stops. For each i between 1 and N, the i+1-st line contains two integers xi and ci, describing the position of the i-th rest stop and the tastiness of the grass there.
It is guaranteed that rF > rB, and 0 < x1 < ⋯ < xN < L. Note that rF and rB are given in seconds per meter!
输出
A single integer: the maximum total tastiness units Bessie can obtain.
样例输入
10 2 4 3
7 2
8 1
样例输出
15
题意：有一个人和一头牛，人的速度是rf，牛的速度是bf，牛的速度一定比人快，在长L的路程中，人将一直走，而牛可以在休息站停留，有N个休息站，每个休息站有鲜度为ci的草，牛在每个休息站停留的时间t 乘鲜度ci可以得到一些鲜度，牛不能在人的后面，只能领先人走，求牛能得到的最大鲜度和
非常简单，只需要每次牛都走到目前最大的鲜度的休息站等着人，就可以不断积累鲜度。等人到了最大鲜度的休息站，牛再找下一个最大鲜度的休息站继续等人。注意结果要用long long
#include<stdio.h>///每次找最大鲜度的休息站，直接到那里等着农夫，然后继续找最大鲜度的休息站
#include<string.h>///注意ans是long long 的
#include<algorithm>
using namespace std;
int n,a[105],dis[105],ans;
bool vis[105];
bool judge()
{
for(int i=0; i<n; i++)
if(!vis[i])return false;
return true;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
ans=0x7fffffff;
memset(dis,0x3f,sizeof(dis));
for(int i=0; i<n; i++) scanf("%d",&a[i]);
sort(a,a+n);
for(int i=1; i<n; i++) dis[i]=a[i]-a[i-1];
for(int i=0; i<n; i++)
{
memset(vis,false,sizeof(vis));
int cnt=0,tmp=i;
while(!judge())
{
cnt++;
// printf("=====%d",tmp);
while(!vis[tmp]&&tmp>=0&&tmp<n)
{
vis[tmp]=true;
if(dis[tmp]<dis[tmp+1])tmp=tmp-1;
else tmp++;
}
tmp=0;
while(vis[tmp]&&tmp<n)tmp++;
}
ans=min(ans,cnt);
}
printf("%d
",ans);
}
}