篱笆专题

分治算法设计:切割篱笆问题

切割篱笆问题 假设有道篱笆用N个同宽的木条拼接而成。因年久失修,有些木板已经折断,因而整个篱笆呈现出参差不齐的轮廓,所以要用新的木板替换。不过为了环保,可以用一部分旧篱笆切割出长方形的木板充当木料。图(b)表示在(a)形状的篱笆中能切割出的最大长方形。给定构成篱笆的各个木板的高度,编写程序计算能够切割出的最大长方形面积。不能斜线切割,即不允许采用如图(c)的切割方法。          图