http://hi.baidu.com/tomspirit/blog/item/22ac940b4b8386c23ac76305.html
http://hplonline20100103.blog.163.com/blog/static/136136434201004004444/
先上函数
void
RectangularArea()
{
int
i;
high[0
] = high[n + 1
] = -1
; //初始化边界,防止越界判错
for
(i = 1
; i <= n; i ++) //把left[], right[]赋值为本身
left[i] = right[i] = i;
for
(i = 1
; i <= n; i ++)
{
while
(high[left[i] - 1
] >= high[i]) //确定l[i]的最高左位置
left[i] = left[left[i] - 1
];
}
for
(i = n; i >= 1
; i --)
{
while
(high[r[i] + 1
] >= high[i]) //确定r[i]的最高右位置
right[i] = right[right[i] + 1
];
}
int
ans = 0
;
for
(i = 1
; i <= n; i ++)
ans = Max(high[i] * (right[i] - left[i] + 1
), ans); //得到最大的连续矩形面积(单位长度是1)
printf("%d/n"
, ans);
}
函数功能是求连续的最大平面矩形的面积。
函数本质是运用栈的思维。
栈:先进后出,栈在写入的时候只用了个top标记栈顶,每次入栈top ++,但实际stack[]已有数组没有变化,top只是一个指向的作用。
而这个函数的left[], right[]数组就等同于top,具有指向作用。
但是得到的left[i]/right[i]是比本来left[i]/right[i]高的最左和最右位置(满足DP的子问题重叠性质),而这个位置就是具有指向意味。
这是关键代码,下面的练习是以之为基础的。
POJ PKU 2559
直接套用上面函数
POJ PKU 3494
2维的最大矩形覆盖,加个连续行的递推判断,注意数组类型要用__int64
if(str)
a[i][j] = a[i-1][j]+1;
POJ PKU 1964
同 3494
POJ PKU 2796
同 2559 底边是high[left[i]] —— high[right[i]]之和,
读入的时候可以预处理个数组 h1[i] += h1[i - 1] + h[i];
POJ PKU 3250
栈,逆向思维,后面的牛被前面的牛看到。
POJ PKU 2082
同2796,恶心的描述,最后画下图就清晰了。
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1001答案
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
北大POJ2305-Basic remains POJ2305-Basic remains