Posted on 2010-12-07 14:41
小小菜鸟蛋 阅读(347)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://poj.org/problem?id=2796
这道题跟2559还有3494都是求最大子矩阵。
对于每个a[i]，求以其为最小值的最大连续的区间，即是以其左边最后一个比它大的数的位置为左边界，以其右边最后一个比它大的数的位置为右边界，例（a[]从1位置开始存放）：
1 6 7 4 5 3 2
a[4] = 4的左边界是2，右边界是5，a[4]的区间是2~5
然后计算出每个数在各自的区间内的值（总和 * a[i]，因为a[i]是这个区间的最小值），枚举出的最大值即为所求。
（算法参见2003国家集训队论文“王知昆：《浅谈用极大化思想解决最大子矩形问题》”算法2，O(nm)的算法。）
注意：结果要用long long保存！代码用到了单调栈扫描。。。嗯嗯，好东西~~
01 #include <cstdio>
02 using namespace std;
03
04 const int N = 100010;
05 int stack[N], a[N], l[N], r[N];
06 long long sum[N]; //sum[i]是前缀和，即前i个数的总和
07
08 int main()
09 {
10 int n;
11 scanf("%d", &n);
12 sum[0] = 0;
13 for (int i = 1; i <= n; i++)
14 {
15 scanf("%d", &a[i]);
16 sum[i] = sum[i-1] + a[i];
17 }
18
19 //求出每个数的左边界
20 int top = 0;
21 stack[0] = 0;
22 a[0] = -1;
23 for (int i = 1; i <= n; i++)
24 {
25 while (a[stack[top]] >= a[i])
26 top--;
27 l[i] = stack[top] + 1;
28 stack[++top] = i;
29 }
30
31 //求出每个数的右边界
32 top = 0;
33 stack[0] = n + 1;
34 a[n+1] = -1;
35 for (int i = n; i >= 1; i--)
36 {
37 while (a[stack[top]] >= a[i])
38 top--;
39 r[i] = stack[top] - 1;
40 stack[++top] = i;
41 }
42
43 long long ans = -1;
44 int id = 0;
45 for (int i = 1; i <= n; i++)
46 {
47 long long temp = (sum[r[i]] - sum[l[i]-1]) * a[i];
48 if (temp > ans)
49 {
50 ans = temp;
51 id = i;
52 }
53 }
54 printf("%lld\n%d %d\n", ans, l[id], r[id]);
55 }