函数功能是求连续的最大平面矩形的面积。
函数本质是运用栈的思维。
栈：先进后出，栈在写入的时候只用了个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，恶心的描述，最后画下图就清晰了。
Read full article from 连续最大区域面积系列 POJ 2082，2559，2796，3494，1964，3250 - gaofen100 - ITeye技术网站
No comments:
Post a Comment