題意：這題是要找最大的矩形面積。

解題思路：這題的關鍵是要找每個條形能夠往左和往右能夠到達的最大長度。我最開始的思路是單調棧去維護，只要入棧的元素比棧頂元素小，棧頂就要出棧，并且知道其最右能夠到達的最遠距離。當要入棧的元素已經找到了位置，那么它左邊的元素所在的位置就是其能到達的最左距離。

這道題比較坑，要用__int64位，而且在當棧為空時，加入的新元素的最左是能夠到達1的，這里我開始沒發現，結果WA到死。。。

這里還有一個dp版本的，感覺實際上和單調棧差不多，都是找最左和最右的距離。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; struct Node {__int64 h;int id; }Stack[maxn]; struct Keep {__int64 l,r,h; }res[maxn]; __int64 n,top,hi[maxn];int main() {while(scanf("%I64d",&n)!=EOF && n){for(__int64 i = 1; i <= n; i++){scanf("%I64d",&hi[i]);res[i].l = res[i].r = i;res[i].h = hi[i];}top = 0;for(__int64 i = 1; i <= n; i++){while(top > 0 && hi[i] <= Stack[top-1].h){res[Stack[top-1].id].r = i - 1;top--;}Stack[top].id = i;Stack[top].h = hi[i];if(top != 0)res[i].l = Stack[top-1].id + 1;else res[i].l = 1; //最容易丟掉的條件,一直WA的原因top++;}while(top > 0){res[Stack[top-1].id].r = n;top--;}__int64 ans = 0;for(int i = 1; i <= n; i++){__int64 area = (res[i].r - res[i].l + 1) * res[i].h;if(area > ans)ans = area;}printf("%I64d\n",ans);}return 0; }

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; int n,l[maxn],r[maxn]; __int64 hi[maxn];int main() {while(scanf("%d",&n)!=EOF && n){for(int i = 1; i <= n; i++)scanf("%I64d",&hi[i]);l[1] = 1; r[n] = n;int t;for(int i = 2; i <= n; i++) //更新每個l[i]{t = i;while(t > 1 && hi[t-1] >= hi[i]) t = l[t-1];l[i] = t;}for(int i = n - 1; i >= 1; i--) //更新每個r[i]{t = i;while(t < n && hi[t+1] >= hi[i]) t = r[t+1];r[i] = t;}__int64 ans = 0, tmp = 0;for(int i = 1; i <= n; i++){tmp = (r[i] - l[i] + 1) * hi[i];if(tmp > ans)ans = tmp;}printf("%I64d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1506（dp || 单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

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