首页 > 代码库 > hdu 1506 Largest Rectangle in a Histogram ((dp求最大子矩阵))
hdu 1506 Largest Rectangle in a Histogram ((dp求最大子矩阵))
# include <stdio.h> # include <algorithm> # include <iostream> # include <math.h> using namespace std; __int64 a[100010],l[100010],r[100010];///l[i]左边连续大于等于a[i]的下标,r[i]右边连续大于等于a[i]的下标,所以对于a[i]的矩形面积为(l[i]-r[i]+1)*a[i]; int main() { __int64 maxn; int i,n; while(~scanf("%d",&n),n) { for(i=1;i<=n;i++) { scanf("%I64d",&a[i]); l[i]=r[i]=i; } for(i=2;i<=n;i++) { while(l[i]>1&&a[l[i]-1]>=a[i]) l[i]=l[l[i]-1]; } for(i=n-1;i>=1;i--) { while(r[i]<n&&a[r[i]+1]>=a[i]) r[i]=r[r[i]+1]; } maxn=-1; for(i=1;i<=n;i++) { if(a[i]*(r[i]-l[i]+1)>maxn) maxn=a[i]*(r[i]-l[i]+1); } printf("%I64d\n",maxn); } return 0; }
hdu 1506 Largest Rectangle in a Histogram ((dp求最大子矩阵))
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。