题解 P1681 【最大正方形II】

· · 题解

其实是最大正方形的变形。

正方形那题是令dp[i][j]是以(i,j)为右下角能得到的最大正方形边长，而这次只要加一个维度判断黑白格就行了。。

令dp[i][j][0/1]是以(i,j)为右下角，且该点上为0/1时能得到的最大正方形边长，则：

1.当a[i][j]=0时

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

2.当a[i][j]=1时

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

这里来着重讲一下为什么状态转移方程中为什么要取min而不是取max。

你想啊，点(i,j)可以从(i-1,j)转移过来，也可以从(i,j-1)转移过来，也可以从(i-1,j-1)转移过来。这3个点要同时兼顾，而(i,j)是决定存在性问题的，如果我取max，我这边可能满足条件，但就不保证其他两边满足条件了。如果你不能理解，我们举个例子就明白了：

假如有一个a数组a[4][4]：

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 0

则dp数组：（这里dp数组用2维表示，为了举例方便） 1

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

2

1 1 1 1
1 0 0 0
0 0 0 0
0 0 0 0

在dp[2][2]中，显然可以从dp[1][2]，dp[2][1]，dp[1][1]这3个点转移，看一下a数组：

1 0
0 1

是可以转移的，于是dp数组

1 1
1 2

dp数组 3

1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 0

等等，dp[3][3]应该为3啊！ 好。

1 1 1 1
1 2 2 2
1 2 3 2
1 2 2 0

那么我们接着看dp[4][3]，发现dp[4][2]=2，dp[3][3]=3，dp[3][2]=2，周围有2个2，1个3，选哪个呢？

好，按照我们之前的惯性思维，如果取max的话，也就是选dp[3][3]的话，则dp数组：

1 1 1 1
1 2 2 2
1 2 3 2
1 2 4 0

发现它并不能构成边长为4的正方形！所以要选边长为2的。 最后dp数组：

1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 0

也就是说，dp[i][j]的选择，是要兼顾dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]的最小值的。如果取最大值的话，显然不能保证dp[i][j]是否还能正确。取最小值是为了能保证dp[i][j]也能满足条件，随着i和j的增大，dp[i][j]一定能保证单调递增的。

#include <stdio.h>
#include <iostream>
#define inf 2e9+7
using namespace std;
int dp[1501][1501][2],a[1501][1501],n,m,s;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    register int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                dp[i][j][0]=min(min(dp[i-1][j][1],dp[i][j-1][1]),dp[i-1][j-1][0])+1;
                s=max(s,dp[i][j][0]);
            }
            if(a[i][j]==1)
            {
                dp[i][j][1]=min(min(dp[i-1][j][0],dp[i][j-1][0]),dp[i-1][j-1][1])+1;
                s=max(s,dp[i][j][1]);
            }
        }
    }
    cout<<s<<endl;
    return 0;
}