这道题感觉就是在描述几何问题 (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黑书上的打造王冠那题。
