1657: [USACO2006 Mar] The singing of Moo Dairy Cow
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 537 Solved: 374
[
Submit][
Status]
Description
Farmer John’s N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This “moo” travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow’s right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.
Farmer John’s n (1 <= n <= 50,000) The cow stands neatly into a column of “howling”. Each cow has a certain height H (1 <= h <= 2000000000), and the volume of the call is v (1 <= v <= 10000). Each cow’s call spreads to both ends, but in each direction, it will only be heard by a nearest cow that is greater than its nearest height, so each call will only be heard by 0, 1,2 dairy cows hear (This depends on whether there is a tall cow on both sides). The total volume that a cow hears is the sum of all the volume it hear. Since some dairy cows have suffered huge volume, Farmer John intends to buy an earmuffs to the most harmful cow, please help him calculate the largest total volume.
Input
* Line 1: A single integer, N.
* Lines 2..N+1: Line i+1 contains two space-separated integers, h and v, for the cow standing at location i.
Line 1: A positive integer n.
No. 2 to N+1 line: Each row includes two integers separated by spaces, which represent the height of the cow standing in the i -i -i -i -statally stand in the team and the volume of her singing when singing.
Output
* Line 1: The loudest moo volume heard by any single cow.
The highest total volume of dairy cows in the team.
The 3rd cow in the
Sample Input
4 2
3 5
6 10
INPUT DETAILS:
Three cows: the first one has height 4 and moos with volume 2, etc.
Sample Output
HINT
team can hear the singing of the first and second cows, so the total volume she can hear is 2+5 = 7. Although her volume was 10 when she sang, there was no cow to hear her singing.
Source
Monoly queue optimized DP.
Do you can do it once.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,h[50005],v[50005],q[50005],ans[50005];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&h[i],&v[i]);
int l=1,r=1;
q[r]=1;
for (int i=2;i<=n;i++)
{
int k=r;
while (k>l&&h[q[k]]<h[i])
k--;
if (h[q[k]]>h[i])
ans[q[k]]+=v[i];
while (r>=l&&h[q[r]]<=h[i])
r--;
q[++r]=i;
}
memset(q,0,sizeof(q));
l=1,r=1;
q[r]=n;
for (int i=n-1;i>=1;i--)
{
int k=r;
while (k>l&&h[q[k]]<h[i])
k--;
if (h[q[k]]>h[i])
ans[q[k]]+=v[i];
while (r>=l&&h[q[r]]<=h[i])
r--;
q[++r]=i;
}
int ma=0;
for (int i=1;i<=n;i++)
ma=max(ans[i],ma);
cout<<ma<<endl;
return 0;
}
perception:
1. Consider the water questions and write clearly. Every time you look for the first number larger than the current, so find it in the queue.