POJ 2796 Feel Good(単調スタック)
1027 ワード
http://poj.org/problem?id=2796
POJ 2559と同様に、計算矩形の長さをプレフィックスとして変更すればいいです。
完全コード:
POJ 2559と同様に、計算矩形の長さをプレフィックスとして変更すればいいです。
完全コード:
/*891ms,2716KB*/
#include
#include
using namespace std;
const int mx = 100005;
__int64 h[mx], sum[mx];
int l[mx], r[mx];
int main()
{
//freopen("in.txt", "r", stdin);
int n, i, j, ansl, ansr;
__int64 ans, tmp;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%I64d", &h[i]);
sum[i] = sum[i - 1] + h[i];
}
for (i = 1; i <= n; ++i)
{
j = i;
while (j > 1 && h[j - 1] >= h[i]) ///
j = l[j - 1]; ///
l[i] = j;
}
for (i = n; i; --i)
{
j = i;
while (j < n && h[j + 1] >= h[i]) ///
j = r[j + 1]; ///
r[i] = j;
}
ans = -1;/// 0
for (i = 1; i <= n; ++i)
{
tmp = h[i] * (sum[r[i]] - sum[(l[i] - 1)]);
if (tmp > ans)
{
ans = tmp;
ansl = l[i];
ansr = r[i];
}
}
printf("%I64d
%d %d
", ans, ansl, ansr);
return 0;
}