USACO3.34Home on the Range（DP）

之前做过一道类似的国际象棋盘神马的。。

统计出以每个1作为右下角的最大正方形那么以大于二到这个最大值之间为边的正方形都可以以这个为右下角累加就可以了

dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1;

 /*

     ID: shangca2

     LANG: C++

     TASK: range

  */

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 int dp[][],num[];

 char s[][];

 int main()

 {

     freopen("range.in","r",stdin);

     freopen("range.out","w",stdout);

     int i,j,n;

     cin>>n;

     for(i = ; i <= n ;i++)

         for(j = ; j <= n ; j++)

         {

             cin>>s[i][j];

             if(s[i][j]=='')

             dp[i][j] =;

         }

     for(i = ; i <= n ; i++)

     {

         for(j =  ; j <= n ; j++)

         {

             if(s[i][j]==''&&s[i-][j]==''&&s[i-][j-]==''&&s[i][j-]=='')

             dp[i][j] = min(min(dp[i-][j],dp[i-][j-]),dp[i][j-])+;

         }

     }

     for(i = ; i <= n ; i++)

         for(j = ; j <= n ;j++)

         {

             for(int g =  ; g <= dp[i][j] ; g++)

             num[g]++;

         }

     for(i = ; i <= n ; i++)

     if(num[i])

     cout<<i<<" "<<num[i]<<endl;

     return ;

 }

巴特西

USACO3.34Home on the Range（DP）

最新文章

热门文章