| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
使用单调栈进行维护栈内数字越来越大,这样在来一个小数字的情况,可以弹出比他大的数字,在这个时候进行计算答案,因为是越来越大的,所以可以保证从弹出点到当前数字都是可以构成矩形的。 代码如下,表达不清,见谅 #include <cstdio> using namespace std; const int MAX_N = 100005; int deep[MAX_N], stack[MAX_N], A[MAX_N], n; int main() { freopen("nimo.in", "r", stdin); while (scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) scanf("%d", &A[i]); A[n+1] = 0; n++; stack[0] = 0; long long ans = 0; deep[0] = 0; int top = 1; for (int i = 1; i <= n; i++) { int depth = i; while (A[i] < stack[top-1]) { long long tmp = (long long)(i - deep[top-1]) * (long long)stack[top-1]; if (tmp > ans) ans = tmp; depth = deep[top-1]; top --; } if (A[i] > stack[top-1]) { stack[top] = A[i]; deep[top] = depth; top ++; } } printf("%lld\n", ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator