題意
思路:DP.
一開始我用二維樹狀數(shù)組去搞。死在最優(yōu)一組數(shù)據(jù)上(全1)。因?yàn)槟菢佑泻芏嗬速M(fèi)的操作。可是想不出什么好辦法，無(wú)奈問了好多人。diy群的神牛們一致說(shuō)dp,baihacker大神的做法好像就這樣的.水平太弱,聽不懂。后來(lái)還是在一個(gè)朋友的指點(diǎn)下領(lǐng)悟了dp的思想。具體如下
設(shè)dp[i][j] 為以(i,j)為左上角的符合情況的邊的最大長(zhǎng)度。那么我們可以得到長(zhǎng)度為k的方陣的個(gè)數(shù)等于那些dp[i][j]>=k的個(gè)數(shù)。
用樣例來(lái)說(shuō)的話
  dp[i][j]如下
  1 0 4 2 3 1
  0 0 3 3 2 1
  1 1 2 2 2 1
  0 0 2 1 1 1
  0 0 1 1 0 1
  1 1 1 0 0 1
  那么2的個(gè)數(shù)就是dp[i][j] >= 2的數(shù)目也就是6(2的個(gè)數(shù))+3(3的個(gè)數(shù))+1(4的個(gè)數(shù))=10
  3和4同理
  那么現(xiàn)在要求的就是所有dp[i][j]了。我們可以得到如下轉(zhuǎn)移方程。
  if(0 == num[i][j])/*num存的是原矩陣*/
   dp[i][j] = 0;/*矩陣含0不符合情況*/
 else
  dp[i][j] = min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])+1;
 到這里基結(jié)束了。官方的有兩種做法，也都是dp。第一種是n^3的,這里就不說(shuō)了。第二種是n^2的。而且空間也比較小，這里貼下。