dp单调栈

题目：hdu1506

题意：一个柱形图，宽均为1.内部最大的矩形的面积。

解答1：刚开始想的是从某个区间内找小的高遍历所有区间找出最大的矩形。但是复杂度太高啦！

    正确的解答：

从每一条出发，分别求出这一条左边连续比它高的和右边连续比它高的坐标。然后遍历一遍便可以求出最大值。

左右！！！可以分别从左边和右边遍历求！！！

以左边为例：

如果左边那个比它高，那么比它左边还高的一定比它还高！

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int MAXN = 100000 + 10; long long int a[MAXN],r[MAXN],l[MAXN]; int main() { long long int n; while(~scanf("%lld",&n) && n) { for(int i = 1;i <= n;i++) scanf("%lld",&a[i]); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); l[1] = 1; r[n] = n; for(int i = 2;i <= n;i++) { int tmp = i; while(tmp > 1 && a[tmp-1] >= a[i]) tmp = l[tmp-1]; l[i] = tmp; } for(int i = n-1;i >= 1;i--) { int tmp = i; while(tmp < n && a[tmp+1] >= a[i]) tmp = r[tmp+1]; r[i] = tmp; } long long int ans = 0; for(int i = 1;i <= n;i++) { ans = max(ans,(long long int)((r[i]-l[i]+1)*a[i])); } printf("%lld\n",ans); } return 0; }

解答2：从左、从右各维护一个单调栈。

单调栈：栈里面的元素是单调的（从小到大或者从大到小）

1、如果栈里元素从小到大：可以直接找到从该位置往左，第一个比它小的元素。

2、如果栈里元素从大到小：可以直接找到从该位置往右，第一个比它大的元素。

这个题，要找到一个位置往左、往右，第一个比它小的元素（如果比它大就可以扩展）

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int MAXN = 100005; long long int a[MAXN],l[MAXN],r[MAXN]; struct g { long long int h,n; }; g q1[MAXN],q2[MAXN]; int main() { int N; while(~scanf("%d",&N) && N) { for(int i = 1;i <= N;i++) scanf("%d",&a[i]); long long int ans = 0; int top = 0; q1[0].h = 0; q1[0].n = 0; q1[++top].h = a[1]; q1[top].n = 1; l[1] = 1; for(int i = 2;i <= N;i++) { if(a[i] > q1[top].h) { q1[++top].h = a[i]; q1[top].n = i; l[i] = i; } else { while(q1[top].h >= a[i] && top >= 1) top--; q1[++top].h = a[i]; q1[top].n = i; l[i] = q1[top-1].n + 1; } } top = 0; q1[0].h = 0; q1[0].n = N+1; q1[++top].h = a[N]; q1[top].n = N; r[N] = N; for(int i = N-1;i >= 1;i--) { if(a[i] > q1[top].h) { q1[++top].h = a[i]; q1[top].n = i; r[i] = i; } else { while(q1[top].h >= a[i] && top >= 1) top--; q1[++top].n = i; q1[top].h = a[i]; r[i] = q1[top-1].n - 1; } } for(int i = 1;i <= N;i++) ans = max(ans,(long long int)((r[i]-l[i]+1)*a[i])); printf("%lld\n",ans); } return 0; }

解答3：依然是单调栈。但是只扫一遍。

有以下结论：

1、如果可以直接入栈，那么它可以向左扩展的长度为1（它自己）。

2、第二个出栈的元素的右宽是前一个出栈的元素的总宽。

3、h的左宽是上一个出栈元素的总宽。

进栈的时候你只能知道它向左扩展的长度（记录下来），出栈的时候你可以算出它向右扩展的长度（出栈意味着它比当前高度要高，就说明它向右扩展不能扩展到当前元素了，那么这个向右扩展的长度是几呢？）

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; int main() { int n,h; int q[100005],l[100005]; while(~scanf("%d",&n)&&n) { long long int ans = 0; memset(q,-1,sizeof(q)); memset(l,0,sizeof(l)); int top = 0; for(int i = 1;i <= n+1;i++) { if(i!=n+1) scanf("%d",&h); else h = 0;//最后把所有的元素弹出栈 if(h > q[top]) q[++top] = h,l[top] = 1;//直接进，向左扩展为1（自己） else//凡是出栈的元素的高度都比h高（向右扩展不到当前的元素） { long long int r = 0; while(h <= q[top]) { ans = max(ans,q[top]*(l[top]+r)); r += l[top--]; } q[++top] = h; l[top] = r + 1;//加上自己 } } printf("%lld\n",ans); } return 0; }