首页 > 代码库 > HDU 1506 Largest Rectangle in a Histogram

HDU 1506 Largest Rectangle in a Histogram

2024-07-14 17:24:25   231人阅读

这个问题姑且也叫做最大子矩阵吧

给一个树状图，求一个最大面积的子矩阵

 

思路是这样的，对于每个单位矩阵，求出左边连续不比它低的矩阵的下标，放在l数组里

同样，再求出右边连续的不比它低的矩阵的下标

这样，对于每个单个矩阵所能得到的最大面积就是 (r[i]-l[i]+1)*a[i]

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 100000 + 5; 8 long long a[maxn], l[maxn], r[maxn]; 9 10 int main(void)11 {12     #ifdef LOCAL13         freopen("1506in.txt", "r", stdin);14     #endif15 16     long long n;17     while(scanf("%I64d", &n) == 1 && n)18     {19         long long ans = -1;20         long long i, t;21         for(i = 1; i <= n; ++i)22             scanf("%I64d", &a[i]);23         l[1] = 1;24         r[n] = n;25         for(i = 2; i <= n; ++i)26         {27             t = i;28             while(t > 1 && a[i] <= a[t-1])29                 t = l[t-1];30             l[i] = t;31         }32         for(i = n-1; i > 0; --i)33         {34             t = i;35             while(t < n && a[i] <= a[t+1])36                 t = r[t+1];37             r[i] = t;38         }39         long long temp;40         for(i = 1; i <= n; ++i)41         {42             temp = (r[i]-l[i]+1)*a[i];43             ans = max(ans, temp);44         }45         printf("%I64d\n", ans);46     }47     return 0;48 }
代码君

 


联系
我们