/* 1017: C03-單調棧算法-最大長方形
時間限制: 1 Sec 內存限制: 128 MB 提交: 17 解決: 10 [提交] [狀態] [討論版] [命題人:外部導入] 題目描述給你一個直方圖，告訴你各個條形矩形的高度，求基線對齊構成的矩形中面積最大的矩形的面積。對于每一個矩形，面積 = h[i]*(j-k+1),其中j，k是左右邊界，h[i]是矩形的高。并且對于j <= x <= k，h[i] <= h[x]。代碼提交鏈接輸入 輸入包含幾個測試用例。每個測試用例描述一個直方圖，并以整數n開始，表示它由多少個矩形組成。你可以假設1 <= n <= 100000。然后按照n個整數h1，…， hn，其中0 <= hi <= 1000000000。這些數字表示直方圖中從左到右排列的矩形的高度。每個矩形的寬度是1。0緊跟最后一個測試用例的輸入。輸出 對于單個行上的每個測試用例輸出，指定直方圖中最大矩形的面積。記住，這個矩形必須與公共基線對齊。樣例輸入7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0樣例輸出8 4000提示我們可以用一個單調棧由低到高來存儲它的高度，并用數組對每個高度記錄一下它前面（包括它自己）一共有多少個比它高的，可以看做它的左寬。 按順序考慮每個高度h，如果h大于棧頂元素，則入棧，此時它大于左面全部的元素，并且將它的寬度初始為1。 否則，將棧內元素出棧，直到滿足上面的條件。出棧時，我們要將出棧元素對之后問題的影響全部考慮進行處理，才能保證做法的正確性。 對于每個高度，它的作用無非兩個：1、以自己作高，向外擴展 2、以別人作高，自己被擴展 由于我們數組中已經記錄了某個高度的左寬，所以我們只需要考慮它能不能向右擴展，如果能，能擴展多少？ 首先，對于第一個出棧的元素來說，它的右寬一定是0。 然而對于第二個，它的右邊有剛才出棧的元素，而且剛才出棧元素的總寬中所涉及的元素一定可以被自己擴展，所以自己的右寬為剛才出棧元素的總寬。 同理可知，第三個出棧元素的右寬為第二個出棧元素的總寬。依次類推。 而當h大于棧頂元素時，h的左寬應該是上次出棧元素的總寬+1（自己），然后入棧。 最后時，將所有元素出棧，即可將所有情況考慮。來源/分類 C03-棧 [提交] [狀態]*/ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<stack> using namespace std; const int Max_N=100008; struct Elem{int id;//向左擴展最遠的下標 long long height;//當前節點高度 Elem(){} //在其他的地方要定義一個Elem類型的變量的時候一定要加 Elem(int _id,long long _height):id(_id),height(_height){} }; int N; long long x[Max_N]; long long Ans(){int i,L_id;long long ans=0;Elem e;stack<Elem> stk;for(i=0;i<=N;i++){L_id=i;while(!stk.empty()&&stk.top().height>x[i]){ans=max(ans,(long long)(i-stk.top().id)*stk.top().height);L_id=stk.top().id;stk.pop();}//由于上面修改了L_id，這里相當于每次加入一個長度為(i-L_id)的長方形//這里枚舉一遍找一個最大值就可以了 stk.push(Elem(L_id,x[i]));}return ans; }int main() {int i;while(cin>>N&&N){for(int i=0;i<N;i++)scanf("%lld",&x[i]);x[N]=-1;cout<<Ans()<<endl;}return 0; }/**************************************************************Problem: 1105User: BlingoLanguage: C++Result: 正確Time:36 msMemory:2880 kb ****************************************************************/

?

1105: B10-動態規劃：直方圖最大長方形

時間限制: 1 Sec??內存限制: 128 MB
提交: 8??解決: 5
[提交] [狀態] [討論版] [命題人:外部導入]

題目描述

給你一個直方圖，告訴你各個條形矩形的高度，求基線對齊構成的矩形中面積最大的矩形的面積。對于每一個矩形，面積 = h[i]*(j-k+1),其中j，k是左右邊界，h[i]是矩形

的高。并且對于j <= x <= k，h[i] <= h[x]。

?

輸入

輸入包含幾個測試用例。每個測試用例描述一個直方圖，并以整數n開始，表示它由多少個矩形組成。你可以假設1 <= n <= 100000。然后按照n個整數h1，…， hn，其中0 <= hi <= 1000000000。這些數字表示直方圖中從左到右排列的矩形的高度。每個矩形的寬度是1。0緊跟最后一個測試用例的輸入。

?

輸出

對于單個行上的每個測試用例輸出，指定直方圖中最大矩形的面積。記住，這個矩形必須與公共基線對齊。

?

樣例輸入

7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0

?

樣例輸出

8 4000

?

提示

我們可以用一個單調棧由低到高來存儲它的高度，并用數組對每個高度記錄一下它前面（包括它自己）一共有多少個比它高的，可以看做它的左寬。
按順序考慮每個高度h，如果h大于棧頂元素，則入棧，此時它大于左面全部的元素，并且將它的寬度初始為1。
否則，將棧內元素出棧，直到滿足上面的條件。出棧時，我們要將出棧元素對之后問題的影響全部考慮進行處理，才能保證做法的正確性。
對于每個高度，它的作用無非兩個：1、以自己作高，向外擴展? ? ? ? 2、以別人作高，自己被擴展
由于我們數組中已經記錄了某個高度的左寬，所以我們只需要考慮它能不能向右擴展，如果能，能擴展多少？
首先，對于第一個出棧的元素來說，它的右寬一定是0。
然而對于第二個，它的右邊有剛才出棧的元素，而且剛才出棧元素的總寬中所涉及的元素一定可以被自己擴展，所以自己的右寬為剛才出棧元素的總寬。
同理可知，第三個出棧元素的右寬為第二個出棧元素的總寬。依次類推。
而當h大于棧頂元素時，h的左寬應該是上次出棧元素的總寬+1（自己），然后入棧。
最后時，將所有元素出棧，即可將所有情況考慮。

?

來源/分類

B10-動態規劃?

?

[提交] [狀態]

轉載于:https://www.cnblogs.com/Tidoblogs/p/11173398.html

總結

以上是生活随笔為你收集整理的动态规划-直方图最大长方形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。