首页 > 代码库 > 51nod1102(单调栈/预处理)
51nod1102(单调栈/预处理)
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1102
题意:中文题诶~
思路:单调栈/预处理 (这篇博客就不细写了啦,只给出代码和转过来的两篇不错的题解,好困了~)
单调栈:http://blog.csdn.net/u012773338/article/details/40265223
代码:
#include <iostream>
#include <stack>
#define ll long long
#define MAXN 50010
using namespace std;
ll a[MAXN], ans=0;
stack<int> st;
int main(void){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i=0; i<n; i++){
cin >> a[i];
}
a[n]=-1;
for(int i=0; i<=n; i++){
if(st.empty()||a[i]>=a[st.top()]){
st.push(i);
}else if(a[i]<a[st.top()]){
int cnt;
while(!st.empty()&&a[i]<a[st.top()]){
ans=max(ans, a[st.top()]*(i-st.top()));
cnt=st.top();
st.pop();
}
st.push(cnt);
a[cnt]=a[i];
}
}
cout << ans << endl;
return 0;
}
预处理:http://blog.csdn.net/queuelovestack/article/details/52326276
代码:
1 #include <iostream>
2 #define ll long long
3 #define MAXN 50010
4 using namespace std;
5
6 ll l[MAXN], r[MAXN], a[MAXN];
7
8 int main(void){
9 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
10 int n;
11 cin >> n;
12 for(int i=1; i<=n; i++){
13 cin >> a[i];
14 }
15 for(int i=1; i<=n; i++){
16 int k=i-1;
17 while(a[i]<=a[k]){
18 k=l[k]-1;
19 }
20 l[i]=k+1;
21 }
22 for(int i=n; i>0; i--){
23 int k=i+1;
24 while(a[i]<=a[k]){
25 k=r[k]+1;
26 }
27 r[i]=k-1;
28 }
29 ll ans=0;
30 for(int i=1; i<=n; i++){
31 ans=max((r[i]-l[i]+1)*a[i], ans);
32 }
33 cout << ans << endl;
34 }
51nod1102(单调栈/预处理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。