首页 / GO / POJ2796 Feel Good（单调栈）

POJ2796 Feel Good（单调栈）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了POJ2796 Feel Good（单调栈），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含960字，纯文字阅读大概需要2分钟。

内容图文

题意：给一个非负整数序列，求哪一段区间的权值最大，区间的权值=区间所有数的和×区间最小的数。

用单调非递减栈在O(n)计算出序列每个数作为最小值能向左和向右延伸到的位置，然后O(n)枚举每个数利用前缀和O(1)计算出以这个数为最小值能得到的最大的区间权。

以前写的单调栈，三个if分支，写得繁繁杂杂的；现在重写了一下，感觉代码简洁了不少：

             1 #include<cstdio>
 2usingnamespace std;
 3#define MAXN 111111
 4int stack[MAXN],top;
 5int l[MAXN],r[MAXN];
 6longlong a[MAXN],s[MAXN];
 7int main(){
 8int n;
 9while(~scanf("%d",&n)){
10for(int i=1; i<=n; ++i) scanf("%d",a+i),s[i]=s[i-1]+a[i];
11         a[++n]=-1;
12for(int i=1; i<=n; ++i){
13             l[i]=r[i]=i;
14while(top && a[stack[top]]>a[i]){
15                 l[i]=l[stack[top]];
16                 r[stack[top]]=i-1;
17                 --top;
18            }
19if(top && a[stack[top]]==a[i]) l[i]=l[stack[top]];
20             stack[++top]=i;
21        }
22int x,y;
23longlong res=-1;
24for(int i=1; i<n; ++i){
25if(res<(s[r[i]]-s[l[i]-1])*a[i]){
26                 res=(s[r[i]]-s[l[i]-1])*a[i];
27                 x=l[i]; y=r[i];
28            }
29        }
30         printf("%lld\n%d %d\n",res,x,y);
31    }
32return0;
33 }

 

原文：http://www.cnblogs.com/WABoss/p/5225379.html

内容总结

以上是互联网集市为您收集整理的POJ2796 Feel Good（单调栈）全部内容，希望文章能够帮你解决POJ2796 Feel Good（单调栈）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1291611.html

来源：【匿名】