`
gaofen100
  • 浏览: 1180121 次
文章分类
社区版块
存档分类
最新评论

连续最大区域面积系列 POJ 2082,2559,2796,3494,1964,3250

 
阅读更多

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,恶心的描述,最后画下图就清晰了。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics