Vijos 1057 盖房子 解题报告

非常经典的正方形最大边长DP，貌似USACO上有一题基本相同的。用f[k,i,j]表示以(i,j)为左上角是否能够构成边长为k的正方形，则可推出状态转移方程：

f[k,i,j]=f[k-1,i,j] and f[k-1,i,j+1] and f[k-1,i+1,j] and f[k-1,i+1,j+1];(1<=k<=min(n,m),1<=i<=n-k+1,1<=j<=m-k+1)

因为f[k]只与f[k-1]有关所以可以使用滚动数组将空间复杂度优化到O(nm)。

R1076485 Accepted 100 From IwfWcf P1057 FPC Vivid Puppy 2008-11-25 16:58:39