每日一dp(1)——Largest Rectangle in a Histogram(poj 2559)使用单调队列优化

Largest Rectangle in a Histogram

题目大意:

有数个宽为1,长不定的连续方格,求构成的矩形中最大面积

/************************************************************************/
/* 

思路1.
当前为n的面积如何与n-1相联系,dp[i][j]=max(dp[i-1][k]) , 0<k<=j
描述:i为方块个数,j为高度
但是此题目的数据对于高度太变态,h,1000000000 ,n,100000
所以不可行(一般计算机为Ghz 相当于1S十几亿运算)

思路2.
此题目寻找的最大面积,对于一个方块来说则是以自己为中心左右两端比自己高
的方块累计和与自己面积的乘积,取最大值。状态转移则可看作已知前面n-1个左边比自己
高的的位置l[i],则如果该下标对应的数据比自己还高,继续往下找。利用了n-1的l[i]中
数值

优化:
使用单调队列
1. 即每次插入都从后往前找,找到不小于自己的,插入并抛弃该位置后面的数据
2. 每次都从队头取元素,并及时淘汰过期数据
此队列具有单调性,最大的永远在队头,对于没用的数据及时删除,过期数据也及时更新

对应到此题目:
q中存放的则是1.2.3.....i-1 的位置,更新的是比[i-1]大的元素,即比[i-1]大的元素都
被更新

*/
/************************************************************************/
#include <iostream>
using namespace std;
const int maxn=5+100000;
int a[maxn];
int q[maxn],l[maxn],r[maxn];
int N,tail,front;
__int64 ans,tmp;
int main()
{
    int i;
	while(scanf("%d",&N),N)
	{
		for(i=1;i<=N;i++)
			scanf("%d",a+i);
		tail=1;front=0;q[1]=1;
		for(i=2;i<=N;i++)
		{
			while( front<tail && a[q[tail]]>a[i] )
				r[q[tail]]=i-1,tail--;
			q[++tail]=i;
		}
		while(front<tail)
			r[q[tail]]=N,tail--;

		tail=1;q[1]=N;
		for(i=N-1;i;i--)
		{
			while( front<tail && a[q[tail]]>a[i] )
				l[q[tail]]=i+1,tail--;
			q[++tail]=i;
		}
		while(front<tail)
			l[q[tail]]=1,tail--;
		ans=0;
		for(i=1;i<=N;i++)
		{
			tmp=r[i]-l[i]+1;
			tmp*=a[i];
			ans=ans>tmp?ans:tmp;
		}
		printf("%I64d\n",ans);

	}
    return 0;
}

每日一dp(1)——Largest Rectangle in a Histogram(poj 2559)使用单调队列优化

时间: 08-08

每日一dp(1)——Largest Rectangle in a Histogram(poj 2559)使用单调队列优化的相关文章

Largest Rectangle in a Histogram (poj 2559 &amp;&amp; hdu 1506 矩形系列 迭代法)

Language: Default Largest Rectangle in a Histogram Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 15608   Accepted: 5040 Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectan

POJ 3926 Parade 单调队列优化DP

来源:http://poj.org/problem?id=3926 题意:行n <= 100, 列m <= 10000,类似于数字三角形,一个人要从底下往上走,每层中可以左右走,但选定方向不能回头(向左不能再向右),每经过一段获得该段的一个值,并走了该段的距离,在同一层走的距离不能超过k.问走到最顶头,获得的总值最大是多少. 分析:dp[i][j]表示走到第i行第j列,获得的值最大为多少.则dp[i][j] = max(dp[i+1][p] + sum(p to j)),sum(p to j)

Largest Rectangle in a Histogram HDU - 1506 (单调栈)

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the

POJ 1821 Fence(单调队列优化DP)

题解 以前做过很多单调队列优化DP的题. 这个题有一点不同是对于有的状态可以转移,有的状态不能转移. 然后一堆边界和注意点.导致写起来就很难受. 然后状态也比较难定义. dp[i][j]代表前i个人涂完前j个位置的最大收益. 然后转移考虑 第i个人可以不刷.dp[i][j]=dp[i-1][j]; 第j个木板可以不刷dp[i][j]=dp[i][j-1]; 然后当c[i].s<=j<=s[i]+l[i]-1时 dp[i][j]=p[i]*j+max(dp[i-1][k]-p[i]*k)其中j-

HDU 1506 Largest Rectangle in a Histogram (dp左右处理边界的矩形问题)

E - Largest Rectangle in a Histogram Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 1506 Appoint description: Description A histogram is a polygon composed of a sequence of rectangles aligned a

POJ 2559 Largest Rectangle in a Histogram (单调栈或者dp)

Largest Rectangle in a Histogram Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 15831   Accepted: 5121 Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal wi

HDU 1056 Largest Rectangle in a Histogram(dp)(求最大的矩形面积)

Problem Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of

POJ2559——DP——Largest Rectangle in a Histogram

Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectang

poj2559 Largest Rectangle in a Histogram

Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectang