Largest Square （简单DP）

emmmm,不知道出处。。。。

题目大意：给你$n imes n$的01矩阵，让你找到最大的0方阵的面积

Sample Input

4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

Sample Output

4

emmm，挺简单的。。。没考虑到全是1的情况WA了挺久的。。。。

1.每个格子能组成的最大方阵都是由上、左、左上3个格子决定的，我们直接取3个的最小边长+1就好了

以下是AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int mac=1500;

int mp[mac][mac],dp[mac][mac];

int main()
{
    int n,m,ans=0;
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            scanf ("%d",&mp[i][j]);
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (mp[i][j]) dp[i][j]=0;
            else dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;
            ans=max(ans,dp[i][j]);
        }
    }    
    printf("%d
",ans*ans);
    return 0;
}

2.先预处理每个格子能向左、向上延伸的最大长度，然后判断能否包含左上角的最大方阵，如果能就直接对$dp[i-1][j-1]$开方，然后+1再平方，如果不能，那么此格的边长就是$min(left[i][j],up[i][j])$

以下是AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int mac=1500;

int mp[mac][mac],dp[mac][mac];
int left[mac][mac],up[mac][mac];//向左，向上延伸的长度

int main()
{
    int n,m,ans=0;
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++){
            scanf ("%d",&mp[i][j]);
            if (!mp[i][j]) dp[i][j]=1;
        }

    for (int i=1; i<=n; i++){
        int cnt=0;
        for (int j=1; j<=m; j++){
            if (mp[i][j]==0) left[i][j]=++cnt;
            else cnt=0;
        }
    }
    for (int j=1; j<=m; j++){
        int cnt=0; 
        for (int i=1; i<=n; i++){
            if (mp[i][j]==0) up[i][j]=++cnt;
            else cnt=0;
        }
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (mp[i][j]) continue;
            if (mp[i-1][j-1]==0){
                int p=sqrt(dp[i-1][j-1]);
                if (left[i][j]<p+1 || up[i][j]<p+1){
                    int use=min(left[i][j],up[i][j]);
                    dp[i][j]=use*use;
                    ans=max(ans,dp[i][j]);
                    continue;
                }
                p++;
                dp[i][j]=p*p;
                ans=max(ans,dp[i][j]);
            }
        }
    }
    printf("%d
",ans);
    return 0;
}