hdu1838Chessboard(DP)

http://acm.hdu.edu.cn/showproblem.php?pid=1838

其实原先不知道这题是DP 我都想不到DP去

想了想没思路看了下题解经典思路：第n大的都是由第n-1大的推出来的

记录以a（i,j)为右下端所能构成的最大棋盘若a[i-1][j]和a[i][j-1]都与它不同而且a[i-1][j-1]与它相同则dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 之所以是最小是因为它要保证能全部构成如：

1011

0101

1010

0101

dp[4][4] 如果可以由dp[3][3]推的话就错了应该是由dp[3][4]推来

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define N 2010

 #define LL __int64

 char s[N][N];

 int dp[N][N];

 int main()

 {

     int i,j,k,n,t;

     scanf("%d",&t);

     while(t--)

     {

         memset(dp,,sizeof(dp));

         scanf("%d",&n);

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

         {

             getchar();

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

             {

                 scanf("%c",&s[i][j]);

                 dp[i][j] = ;

             }

         }

         int maxz=;

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

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

             {

                 if(s[i][j]!=s[i-][j]&&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-])+;

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

                 maxz = max(dp[i][j],maxz);

             }

         LL num=;

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

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

             if(s[i][j]==''&&dp[i][j]==maxz)

             num++;

         cout<<maxz<<" "<<num<<endl;

     }

     return ;

 }

巴特西

hdu1838Chessboard(DP)

最新文章

热门文章