这道题感觉就是在描述几何问题 (largest rectangle )，当然是用代数方式。
第一个想到的方法是DP，O(n^2)，同枚举没什么区别。
再一个容易想到的办法，按高度，最高的有机会“自成一家”，otherwise, the taller part is droped, the remaining is added to taller one on it's sides, and so one. Time complexity: O(nlgn)[sort]+O(n)[merge] = O(nlgn). max N is 50000, worth a try.
The O(n) algorithm given by report: from left to right calculate the area of one higher than both sides, then merge with higher side, and go on.
#include <iostream>
#define N 50001
using namespace std;
struct Rect
{
int w,h;
};
Rect rect[N];
int top; // use it as a stack
int main()
{
int n;
__int64 s;
Rect tmp,tmp2;
while (scanf("%d",&n)!=EOF)
{
if (n==-1) break;
rect[0].h = rect[0].w = 0;
s = 0;
top =1;
for (int i=1; i<=n; ++i)
{
scanf("%d%d",&tmp.w,&tmp.h);
while (tmp.h < rect[top-1].h)
{
if (rect[top-1].h*rect[top-1].w>s)
s = rect[top-1].h*rect[top-1].w;
if (rect[top-2].h > tmp.h)
{
rect[top-2].w +=rect[top-1].w;
--top;
}
else
{
tmp.w += rect[top-1].w;
--top;
break;
}
}
rect[top] = tmp;
++top;
}
while (top>=2)
{
if (rect[top-1].h*rect[top-1].w>s)
s = rect[top-1].h*rect[top-1].w;
rect[top-2].w += rect[top-1].w;
--top;
}
printf("%I64d/n",s);
}
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=1755 这道题用另一方式描述了一道计算几何问题。
总的说来是图形化的描述。
做这题时想到了LRJ黑书上的打造王冠那题。