Apro1066 的博客

Apro1066 的博客

题解 P1681 【最大正方形II】

posted on 2019-08-21 22:44:38 | under 题解 |

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

正方形那题是令$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;
}