题目描述: Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0. Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑ 0<=j<=i-1wj <= x <= ∑ 0<=j<=iwj} Again, define set S = {A| A = WH for some W , H ∈ R + and there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained in set B}. Your mission now. What is Max(S)? Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy. But for this one, believe me, it's difficult.
题意简单理解就是有n个并排放置的矩形，长宽分别为w,h，要求连在一起的最大面积；
输入：先输入一个n表示矩形个数，然后依次输入每个矩形的w,h，当n=-1时输入结束。
输出：最大面积；
样例：
input:
3 1 2 3 4 1 2 3 3 4 1 2 3 4 -1 ouput:
12 14 同样是单调队列和单调栈的应用，当当前的矩形h高于前一个矩形的h，前面的宽度就肯定无法覆盖到这里，所以我们维护一个单调增的序列，并在弹出栈顶元素时更新当前能最大覆盖的w，每次弹出时计算一次面积最后得到最大值。
AC代码:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<string> #include<stack> #include<queue> #include<algorithm> using namespace std; const int MAXM=100010; const int INF=1e9+7; struct square { int width; int height; }; int n; int main() { while(scanf("%d",&n)!=EOF) { if (n==-1) break; int ans=-INF; stack<square > s1; for (int i=1;i<=n;i++) { int w,h; scanf("%d%d",&w,&h); int tmp=0; while(!s1.empty()&&h<=s1.top().height) { int tot=s1.top().height*(s1.top().width+tmp); if (tot>ans) ans=tot; tmp+=s1.top().width; s1.pop(); } struct square s; s.height=h; s.width=w+tmp; s1.push(s); } int tmp=0; while(!s1.empty()) { int tot=s1.top().height*(s1.top().width+tmp); if (tot>ans) ans=tot; tmp+=s1.top().width; s1.pop(); } printf("%d\n",ans); } return 0; }
