题解 P1681 【最大正方形II】
Apro1066
2019-08-21 22:44:38
其实是最大正方形的变形。
正方形那题是令$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]$一定能保证单调递增的。
```cpp
#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;
}
```