本文主要是介绍NKOJ 2150 广告印刷 单调队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 【单调队列】广告印刷 Time Limit:10000MS Memory Limit:65536K Description 最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N(N<=400000)个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，0<=Hi<=1,000,000并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。 Input 第一行，一个整数N Output 一个整数，表示最大面积 Sample Input
6
5 8 4 4 8 4 Sample Output
24 Source
|
[Submit] [Go Back] [Status] [Discuss]
Home Page 
Go Back 
To top
求正反两次单调队列即可获得最大值
ACcode：
#include <bits/stdc++.h>
#define maxn 400004
#define ll long long
using namespace std;
int a[maxn],dp[maxn];
ll lmax[maxn],rmax[maxn];
int main(){int n;while(~scanf("%d",&n)){for(int i=0,real=1;i<n;++i){scanf("%d",&a[i]);if(i==0)dp[i]=-1;while(real>1&&a[dp[real-1]]>=a[i])real--;lmax[i]=i-dp[real-1]-1;dp[real++]=i;}dp[0]=n;for(int i=n-1,real=1;i>=0;--i){while(real>1&&a[dp[real-1]]>=a[i])real--;rmax[i]=dp[real-1]-i-1;dp[real++]=i;}ll ans=-0x3f3f3f3f;for(int i=0;i<n;++i)ans=max(ans,(1+lmax[i]+rmax[i])*a[i]);cout<<ans<<'\12';}return 0;
}
这篇关于NKOJ 2150 广告印刷 单调队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
