POJ 2796：Feel Good 单调栈经典题
|
题目大意：给出一组数字，求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点。 Description Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of life.? A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.? Bill calls this value the emotional value of the day. The greater the emotional value is,the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period,multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.? Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so. Input The first line of the input contains n - the number of days of Bill's life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1,a2,... an ranging from 0 to 106?- the emotional values of the days. Numbers are separated by spaces and/or line breaks. Output Print the greatest value of some period of Bill's life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill's life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them. Sample Input 6 3 1 6 4 5 2 Sample Output 60 3 5 单调栈: 顾名思义就是在入栈时遵循单调原则，可以求出一个元素向左（或向右）所能扩展到的最大长度，并不是说在这一段区间内是单调的，而是保证在该区间内该元素一定是最大或最小；? 单调栈主要是大家要自己枚举，需要找到每个元素最左能扩展到那 ，最优能扩展到那，当然最小的是你枚举的那个元素。? 我们有如下的性质：? 1. 如果当前元素大于前一元素，那么前一元素能扩展到当前元素，同时说明前面的数对当前元素来说是没有贡献的? 2。如果当前元素等于前一元素，那么前一元素也能扩展到当前元素，同时说明前面的元素是可以被忽略的? 3。如果当前元素小于前一个元素，那么前面至少有一个元素不能扩展到当前元素的位置，那么这些不能继续扩展的元素的存在显的没有什么意义了，不妨删除它。? 我们得到两条结论：? 1。一旦一个元素已经进入栈中那么这个元素向左扩展的位置就确定下来了.? 2。一旦一个元素出栈被弹出栈,那么这个元素向右扩展的位置也确定下来了. 和POJ 2559一样，把计算矩形的长改为前缀和就行。 /* POJ 2796 单调队列 维护一个单调不降的序列，然后每次遇到比top小的数时进行 * 出栈操作并且把值更新下 * * */ #include #include #include #include #include #include #include #include using namespace std; const int INF = ~0u>>1; typedef pair #define MID(x,y) ((x+y)>>1) #define iabs(x) ((x)>0?(x):-(x)) #define REP(i,a,b) for(int i=(a);i<(b);i++) #define FOR(i,b) for(int i=(a);i<=(b);i++) #define pb push_back #define mp make_pair #define print() cout<<"--------"< typedef long long ll; ll st[100100],a[100100],sum[100100]; int main(){ int n; while (~scanf("%d",&n)){ memset(a,sizeof(a)); memset(st,sizeof(st)); for (int i = 1; i <= n; i++){ scanf("%lld",&a[i]); sum[i] += sum[i-1] + a[i]; } int top = 0; a[n + 1] = -1; ll tmp,ans = -1; int l,r; for (int i = 1; i <= n + 1; i++){ while (top != 0 && a[st[top]] > a[i]){ tmp = a[st[top]] * (sum[i-1] - sum[st[top - 1]]); if (tmp > ans){ ans = tmp; l = st[top-1] + 1; r = i - 1; } top --; } top ++; st[top] = i; } printf("%lldn%d %dn",ans,l,r); } return 0; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |