题解 P2422 【良好的感觉】

· · 题解

【思路】

单调栈
这不就是单调栈板子题吗？

【前缀思想】

某个区间的总和？
很显然可以用前缀和搞定
嗯，没有问题
区间不定可大可小？
单调队列明显不行，可标签就是单调队列+DP
怀疑自己是自己太弱
继续想单调队列
发现貌似单调栈好像更好写

【中心思想】

因为这是某个大小不定的区间里面的最小值乘以区间总和
总和先不考虑
一个前缀和轻轻松松
考虑区间的最小值
一开始想枚举区间大小
但是区间大小太多种，而且组合方式也很多
所以很麻烦
但是可以这样想
最小值一共有多少种可能 ？
就一共只由n种
那枚举最小值n是多少岂不美哉？
枚举出来最小值之后就需要找区间了
因为没有负数
所以区间越大越好就找最大区间

【最大区间】

最大区间的前提是什么？
里面的值都要大于等于枚举出来的最小值
这是没有任何问题的
那么这个最大区间的两边边界一定是小于这个最小值的数
所以可以用单调栈来解决！！！

【实现】

单调栈单调的过程
如果手中这个元素小于栈顶的话
那栈顶元素当最小值的时候，
他的右边界只能到达手中这个元素位置前面的那一个元素
不然最小值这个称号就会易主了
如果手中这个元素大于栈顶的话
那手中这个元素当最小值的时候，左边的边界只能到达
栈顶元素右边的那个位置
不然同上最小元素的称号也会易主
这样就可以很轻松的求出最大区间
然后用前缀和求出区间总和乘以区间最小元素
比较最大值
输出就好了

【完整代码】

#include<iostream>
#include<cstdio>
#include<stack>
#define int long long
using namespace std;
const int Max = 100005;
int a[Max];
int sum[Max];
int l[Max];
stack<int>s;
signed main()
{
    int n;
    cin >> n;
    for(register int i = 1;i <= n;++ i)
        cin >> a[i],sum[i] = sum[i - 1] + a[i];
    int M = 0;
    for(register int i = 1;i <= n;++ i)
    {
        while(!s.empty() && a[i] < a[s.top()])
        {
            M = max(M,(sum[i - 1] - sum[l[s.top()]]) * a[s.top()]);
            s.pop();
        }
        if(!s.empty())
        l[i] = s.top();
        else
        l[i] = 0;
        s.push(i);
    }
    cout << M << endl;
    return 0;
}