hdu 1506 (dp) Largest Rectangle in a Histogram

本文主要是介绍hdu 1506 (dp) Largest Rectangle in a Histogram，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一直long long 过不去。。。然后，改成__int64竟然过了。。。

1505的减弱版。。

分别计算a[i]点的左右比它高的所有相邻的点的长度就可以了。

用l[i],r[i]表示左右的长度。

a[l[i]-1]>=a[i]     l[i]=l[l[i]-1];

a[r[i]+1]>=a[i]   r[i]=r[r[i]+1];

#include <iostream>
using namespace std;
__int64 l[100005],r[100005];
__int64 a[100005];
int main()
{int n;while(scanf("%d",&n)==1&&n){for(int i=0;i<n;i++)l[i]=r[i]=i;for(int i=0;i<n;i++){scanf("%I64d",&a[i]);while(l[i]-1>=0&&a[l[i]-1]>=a[i])l[i]=l[l[i]-1];}for(int i=n-2;i>=0;i--)while(r[i]+1<n&&a[r[i]+1]>=a[i])r[i]=r[r[i]+1];__int64 max=0;for(int i=0;i<n;i++)if((r[i]-l[i]+1)*a[i]>max)max=(r[i]-l[i]+1)*a[i];printf("%I64d\n",max);}return 0;
}

这篇关于hdu 1506 (dp) Largest Rectangle in a Histogram的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---