SGOI8之《恺撒的规划》解题报告
   
一． 题目简述：
　　的矩阵，0表示空地，1表示障碍，有p种规格的正方形，问对于每一种正方形在矩阵种各有几种不同的放法。

二. 分析：
　　由于问题规模比较大，故一一枚举必定会超时，因此要寻找更高效的算法。
　　我们并将的矩阵中所有不包含障碍的正方形分成（）类。划分的标准是，若某一个正方形的右下角坐标为（I,j）,那么称该正方形为（I,j）类正方形。我们发现，在（I,j）类中，若正方形的最大规格为s(I,j),那么该类一定包含了规格为1…..s(I,j)的正方形。因此我们只要能快速地计算出所有的s(I,j)， 那么问题就得以解决。
　　s(I,j) 是可以利用递推式计算出的：
　　　　1． 当第（I,j）格为1时,s(I,j)=0
　　　　2． 当第（I,j）格为0时，s(I,j)=min{s(I-1,j-1),s(I-1,j),s(I,j-1)}+1
　　边界条件：s(0,I)=0 (0<=I<=m) , s(I,0)=0 (0<=j<=n)
　　对与任意I,j(1<=I<=m,1<=j<=n) ,若s(I,j)>0 那么，d(s(I,j))=d(s(I,j))+1 （d数组用于计算答案）
　　那么的正方形的放法数为∑d(j) (1<=j<=I)

三．复杂度分析：
　　因为一共有个状态，每次状态转移仅要O(1) 的时间，故总体时间复杂度为 O().而0<=m,n<=2000,故时间上没有问题。因为s(I,j)的状态转移只依赖s(I-1,j-1),
s(I-1,j),s(I,j-1),故只需要O(n) 的空间。

   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有