USACO 5.3.4Big Barn

中文题意
此题我用的是dp做的,因为数据不大,所以直接开两个二维数组,一个记录农场信息,一个是dp用的矩阵.dp[i][j]表示右下角是[i,j]的正方形的边长.我的农场信息是,farm[i][j]=1表示无树 而=0表示有树.那么dp的二维数组首先初始化第一行和第一列,如果第一行的某个点有树,那么这个点的dp值为0,否则为1.递推方程是dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1[if farm[i][j]==1]否则dp[i][j]=0;然后输出dp的最大值就OK了.当然这里dp的二维数组完全没必要,因为dp[i][j]只与当前行,上一行有关,我们完全可以只开一个2*N的数组就ok了.