最大正方形 同luogu1387

这道题下面这么写就够了（n<=100）暴力，枚举

#include<bits/stdc++.h>

#define ULL unsigned long long

#define MAXN 100+5

#define f(i,j,n) for(register int i=j;i<=n;i++)

using namespace std;

ULL T,a[MAXN][MAXN],n,m;

int q(int i,int j,int k,int l) {

    f(p,i,j)

    f(q,k,l)

    if(a[p][q]==) return ;

    return min(j-i+,l-k+);

}

void solve(int T) {

    int ans=;

    while(T--) {

        memset(a,,sizeof(a));

        cin>>n>>m;

        f(i,,n)

        f(j,,m) {

            int x;

            cin>>x;

            a[i][j]=x;

        }

        f(i,,n)

        f(j,i,n)

        f(k,,m)

        f(l,k,m)

        ans=max(ans,q(i,j,k,l));

        cout<<ans<<endl;

    }

}

int main() {

    solve();

    return ;

}

然后如果说要提升的话（n<=1000） 二维前缀和

#include<iostream>

    #include<cstdio>

    #include<cctype>

    #include<cstring>

    #include<algorithm>

    using namespace std;

    int n,m,map[][];

    int sum[][];

    void pre(){

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

            for(int j=;j<=m;j++)

                sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+map[i][j];

    }

    int main(){

        scanf("%d%d",&n,&m);

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

            for(int j=;j<=m;j++)

                scanf("%d",&map[i][j]);

        pre();

        int ans=-;

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

            for(int j=;j<=m;j++)

                for(int l=;l<=min(n,m);l++){

                    int rx=i+l-,ry=j+l-;

                    if(i-+l>n||j-+l>m||sum[rx][ry]-sum[rx][j-]-sum[i-][ry]+sum[i-][j-]!=l*l) break;

                    if(ans<l) ans=l;

                }

        printf("%d",ans);

        return ;

    }

然后在提升->（n<=5000）动态规划 DP

#include<bits/stdc++.h>

using namespace std;

int a[][],f[][],ans;

int main()

{

    int n,m;

    cin>>n>>m;

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

    {

        for(int j=;j<=m;j++)

        {

            cin>>a[i][j];

            if(a[i][j]==) f[i][j]=min(min( f[i][j-],f[i-][j]),f[i-][j-])+;

            {

                ans=max(ans,f[i][j]);

            }

        }

    }

    cout<<ans;

    return ;

}