ACM PKU 2559 Largest Rectangle in a Histogram http://acm.pku.edu.cn/JudgeOnline/problem?id=2559

关于覆盖，用DP是一种很不错的解决方法，时效也很不错....

这题目把图一画就很明确了，没有说明的必要了。

#include <iostream> using namespace std; __int64 height[100001]; int main () { int n; int left[100001]; int right[100001]; __int64 max=0,temp=0; while (scanf("%d",&n) && n) {int i=0;memset(height,0,sizeof(height));right[0]=0;left[n-1]=n-1;for(; i<n;i++){scanf("%I64d",&height[i]); }for(i=1;i<n;i++){right[i]=i;while(right[i]>0&&height[i]<=height[right[i]-1])right[i]=right[right[i]-1];}max=height[n-1];for(i=n-2;i>=0;i--){left[i]=i;while(left[i]<n-1&&height[left[i]+1]>=height[i])left[i]=left[left[i]+1];temp=(left[i]-right[i]+1)*height[i];if(temp>max)max=temp;}printf("%I64d\n",max);} return 0; }

转载于:https://www.cnblogs.com/Chinese-Coder-Clarence/articles/2039235.html

总结

以上是生活随笔为你收集整理的ACM PKU 2559 Largest Rectangle in a Histogram http://acm.pku.edu.cn/JudgeOnline/problem?id=2559的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。