題意
思路:DP.
一開始我用二維樹狀數(shù)組去搞。死在最優(yōu)一組數(shù)據(jù)上(全1)。因為那樣有很多浪費的操作。可是想不出什么好辦法，無奈問了好多人。diy群的神牛們一致說dp,baihacker大神的做法好像就這樣的.水平太弱,聽不懂。后來還是在一個朋友的指點下領(lǐng)悟了dp的思想。具體如下
設(shè)dp[i][j] 為以(i,j)為左上角的符合情況的邊的最大長度。那么我們可以得到長度為k的方陣的個數(shù)等于那些dp[i][j]>=k的個數(shù)。
用樣例來說的話
  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的個數(shù)就是dp[i][j] >= 2的數(shù)目也就是6(2的個數(shù))+3(3的個數(shù))+1(4的個數(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的,這里就不說了。第二種是n^2的。而且空間也比較小，這里貼下。