ZJU/ZOJ 2067 White Rectangles 解题报告

题目大意是给出由黑白两色摆成的正方形图片，输出其中的白色矩形的总数。

用O(n^2)的时间预处理出每个白色点位的最大可扩展高度，这样即可在O(n^3)的时间内进行DP。用f[i,j]表示以第i列到第j列为下底的矩形最大高度，显然f[i,j]=min(f[i,j-1],h[r,j]);其中r为当前所处行。累加计算f[i,j]即可，一旦f[i,j]=0即可退出循环。

3021897 2008-08-04 22:47:20 Accepted 2067 FPC 00:00.20 436K IwfWcf