题解 P1387 【最大正方形】

Panthera_AFO · 2018-10-25 08:29:16 · 题解

这道题可谓DP经典，只是我看楼上几个题解都不太详细，在此给一个证明吧（或者说详细讲解？）

希望不要说窝算法重复

这张图用画图画了半天，将就着看吧

以下是我的AC代码

#include<cstdio>
#include<iostream>
int const maxn=111;
int f[maxn][maxn],n,m,ans;
int min(int x,int y,int z)
{
    return std::min(std::min(x,y),z);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int a,j=1;j<=m;j++)
            scanf("%d",&a),f[i][j]=a?min(f[i-1][j],f[i][j-1],f[i-1][j-1])+a:0,ans=std::max(ans,f[i][j]);
    printf("%d",ans);
    return 0;
}