最大矩形:柱状图是由一些宽度相等的长方形下端对齐后横向排列得到的图形。现在有由n个宽度分别为wi,高度分别为hi的长方形从左到右依次排列组成的柱状图。问里面包含的长方形的最大面积是多少。
4.4常用技巧精选(二)
栈
讨厌中国人出的英文题,明明可以用形象的语言去描述,却非要用一堆排版粗劣的公式,还自以为很幽默。
画个图一目了然:
对于这三个矩形,红色阴影矩形即为最大。
不妨先跟书上的例题做个比较,例题中矩形的宽都是1:
所以在出结果的时候只需
res = max(res, (long long)h[i] * (R[i] - L[i]));
R[i] – L[i]就能得到最终矩形的宽度,如果我们将题目中的宽度与R和L对应起来,比如说用宽度的累计数组代替:
res = max(res, (long long) h[i] * (w_sum[R[i]] - w_sum[L[i]]));
就能直接用书上的模板解题了。
书上例题
复习一下书上的思想:
设面积最大的长方形的左端是L,右端是R,高度是H。如果hL-1≥H,那么左端点就可以更新为L-1,从而可以得到更大的长方形。这与假设矛盾,因此L是
的最大的j,R是
的最小的j(>i)。我们把这两个值分别表示为L[i]和R[i]。则
L[i]=(j≤i并且hj-1<hi的最大的j)
R[i]=(j>i并且hj>hi的最小的j)
如果能求出L[i]和R[i],那么最大的面积就是max{hi×(R[i]-L[i])|0≤i
设在栈里的元素从上到下的值为xi,则xi>xi+1且
在计算L[i]时,首先,当栈顶的元素j满足hj≥hi,则不断取出栈顶元素。若栈为空,则L[i]=0,若hj<hi,则L[i]=j+1。然后把i压入栈中。
重点是维护一个单调递减栈,于是改改就过了
#include <iostream> using namespace std; #define MAX_N 50000 // 输入 int N; int w[MAX_N], h[MAX_N]; int w_sum[MAX_N + 1]; int L[MAX_N], R[MAX_N]; int st[MAX_N]; // 栈 void solve() { // 计算L int t = 0; // 栈的大小 for (int i = 0; i < N; i++) { while (t > 0 && h[st[t - 1]] >= h[i]) t--; L[i] = t == 0 ? 0 : (st[t - 1] + 1); st[t++] = i; } // 计算R t = 0; for (int i = N - 1; i >= 0; i--) { while (t > 0 && h[st[t - 1]] >= h[i]) t--; R[i] = t == 0 ? N : st[t - 1]; st[t++] = i; } long long res = 0; // 注意防止溢出 for (int i = 0; i < N; i++) { res = max(res, (long long) h[i] * (w_sum[R[i]] - w_sum[L[i]])); } printf("%lld\n", res); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif while (~scanf("%d", &N) && N >= 0) { for (int i = 0; i < N; ++i) { scanf("%d%d", w + i, h + i); w_sum[i + 1] = w_sum[i] + w[i]; } solve(); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; }
16472007 | hankcs | 2082 | Accepted | 1120K | 94MS | C++ | 1109B | 2017-01-13 11:34:40 |
一发入魂,真痛快。
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 2082 Terrible Sets 题解《挑战程序设计竞赛》