题目链接
题意
对于一个长度为(n)的非负整数数列(a_1,a_2,…,a_n)，求(max_{1≤l≤r≤n}f(l,r)), 其中
[f(l,r)=min(a_l,a_{l+1},…,a_r)×(a_l+a_{l+1}+⋯+a_r)
]
思路
显然，最小值必为数列中的某个数，所以题目转化为：
对于数列中的 每个数，找 使其 为区间最小值的 最大的区间，即该点向左向右最远能延伸到的地方
// 是不是和那道找最大矩形面积如出一辙？
法一：dp
用(l[ ])和(r[ ])记录当前位置向左向右延伸的最远距离。
从左向右计算(l[ ])，计算当前位置的(l[ ])值时沿着之前计算并记录下来的信息跳着向前找。
(r[ ])值同理。
法二：单调栈
只需一次遍历，维护一个单调增的栈。
当前栈中每一个元素的右端点至少都是当前位置，左端点则都是之前已记录位置。
踢掉元素进行更新的时候要注意将踢掉元素的左端点的值继承下来，因为踢掉它们意味着它们比当前元素要大，所以当前元素的左端点必然能延伸到它们能延伸到的位置。
由上述过程可看出，当每个元素被踢出来时，其左端点值和右端点值都最终确定了，因而可以计算以它为最小值的这一段对应的答案。
此外，还要注意在最后补上一个最小元素（-1），这是为了保证所有的元素最终都能被踢出来。
说的可能有点抽象...拿样例来说吧
3 1 6 4 5 2
// 以下符号中圆括号中的值代表左端点，方括号中的pair代表左端点和右端点
// 注意：为了看起来直观，下例中栈中的元素均以其对应的值替代，实际操作中真正记录的是下标
*step 1.*
3进栈
3(1)
*step 2.*
踢掉3[1,1]，1进栈
1(1)
*step 3.*
6进栈
1(1), 6(3)
*step 4.*
踢掉6[3,3]，4进栈
1(1), 4(3)
*step 5.*
5进栈
1(1), 4(3), 5(5)
*step 6.*
踢掉5[5,5]，踢掉4[3,5]，2进栈
1(1), 2(6)
*step 7.*
踢掉2[6,6]，踢掉1[1,6]，-1进栈
-1(7)
Code
法一
#include <stdio.h>
#define maxn 100010
using namespace std;
typedef long long LL;
int a[maxn], l[maxn], r[maxn];
LL pre[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), pre[i] = pre[i-1] + a[i];
l[1] = 0;
for (int i = 2; i <= n; ++i) {
int p = i-1;
while (p && a[p] >= a[i]) p = l[p];
l[i] = p;
}
r[n] = n+1;
for (int i = n-1; i > 0; --i) {
int p = i+1;
while (p != n+1 && a[p] >= a[i]) p = r[p];
r[i] = p;
}
LL ans = -1;
int ll, rr;
for (int i = 1; i <= n; ++i) {
LL temp = (pre[r[i]-1] - pre[l[i]]) * a[i];
if (temp > ans) ans = temp, ll = l[i]+1, rr = r[i]-1;
}
printf("%lld
%d %d
", ans, ll, rr);
return 0;
}
法二
#include <stdio.h>
#include <iostream>
#define maxn 100010
using namespace std;
typedef long long LL;
int a[maxn], st[maxn], l[maxn];
LL pre[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
pre[i] = pre[i-1] + a[i];
}
int top = 0;
a[++n] = -1;
LL ans = -1; int lll, rrr;
for (int i = 1; i <= n; ++i) {
int x, ll=i, rr=i-1;
while (top && a[i] < a[st[top-1]]) {
x = st[--top], ll = l[x];
LL temp = a[x] * (pre[rr] - pre[ll-1]);
if (temp > ans) ans = temp, lll = ll, rrr = rr;
}
l[i] = ll; st[top++] = i;
}
printf("%lld
%d %d
", ans, lll, rrr);
return 0;
}
后话
既然上面都提到了最大矩形面积...写博客的时候就一时兴起回头翻了翻
hdu 1505 1506 2870 dp小礼包
原来那个时候我就学过一遍单调栈的做法啊...(叹
不管不管现在的代码至少比以前写得好看(