BZOJ 1657 [Usaco2006 Mar]Mooo 奶牛的歌声：单调栈【高度序列】

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1657

题意：

　　Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。

　　每头奶牛有一个确定的高度h(1<=h<=2000000000)，叫的音量为v (1<=v<=10000)。

　　每头奶牛的叫声向两端传播，但在每个方向都只会被身高严格大于它的最近的一头奶牛听到，所以每个叫声都只会被0，1，2头奶牛听到（这取决于它的两边有没有比它高的奶牛）。

　　一头奶牛听到的总音量为它听到的所有音量之和。

　　自从一些奶牛遭受巨大的音量之后，Farmer John打算买一个耳罩给被残害得最厉害的奶牛，请你帮他计算最大的总音量。

题解：

　　单调栈。

　　单调性：

　　　　对于每一个位置，要找到它左边（或右边）第一个比它大的元素。

　　　　所以从栈顶到栈底，高度依次递增。（因为如果出现下降的元素，肯定是没有用的）

　　所以分别从左到右和从右到左，做两次单调栈就好了，最后统计最大的答案。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stack>

 #define MAX_N 50005

 using namespace std;

 int n;

 int ans=;

 int h[MAX_N];

 int v[MAX_N];

 int tot[MAX_N];

 stack<int> stk;

 void read()

 {

     cin>>n;

     for(int i=;i<n;i++)

     {

         cin>>h[i]>>v[i];

     }

 }

 void solve()

 {

     memset(tot,,sizeof(tot));

     for(int i=;i<n;i++)

     {

         while(!stk.empty() && h[stk.top()]<=h[i]) stk.pop();

         if(!stk.empty()) tot[stk.top()]+=v[i];

         stk.push(i);

     }

     while(!stk.empty()) stk.pop();

     for(int i=n-;i>=;i--)

     {

         while(!stk.empty() && h[stk.top()]<=h[i]) stk.pop();

         if(!stk.empty()) tot[stk.top()]+=v[i];

         stk.push(i);

     }

     for(int i=;i<n;i++)

     {

         ans=max(ans,tot[i]);

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 1657 [Usaco2006 Mar]Mooo 奶牛的歌声：单调栈【高度序列】

最新文章

热门文章