【每日DP】day3 P1387 最大正方形（奇怪的DP增加了 / 二维前缀和）难度⭐⭐★

奇怪的DP增加了

这道题，刚看见真是一脸懵逼，看了题解才明白。

本题中神奇的转移方程是：
$f\left[i\right]\left[j\right]=min\left(min\right(f\left[i\right][j-1],f[i-1]\left[j\right]),f[i-1\left]\right[j-1\left]\right)+1$f[i][j]=min(min(f[i][j−1],f[i−1][j]),f[i−1][j−1])+1

其中 $f\left[i\right]\left[j\right]$f[i][j]表示的是以 $i$i 行 $j$j 列这个点为右下角，所能构成的正方形的最大边长。
只有当这个点是1的时候才能组成正方形，才能去更新 $f$f 数组。
若 $f$f 数组:

?  ?  ?  ?
?  ?  2  1
?  ?  3  ?
?  ?  ?  ?

则说明原矩阵为：

1  1  1  0
1  1  1  1
1  1  1  1
?  ?  ?  ?

用 $ans$ans 来找最大的 $f\left[i\right]\left[j\right]$f[i][j]即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2000+7;
const ll mod=100000000;
ll n,m,f[N][N],a,ans;
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%lld",&a);
            if(a)f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;#如果是0就直接为1了新开一个正方形
            ans=max(ans,f[i][j]);
        }
    printf("%lld\n",ans);
    return 0;
}

同样这道矩阵可以用二维前缀和来做主要是为了练习一下二位前缀和，还不如DP呢

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(int i=s;i<=t;++i)
#define lver(i,t,s) for(int i=t;i>=s;--i)
using namespace std;
typedef long long ll;
const ll N=3e3+7;
const ll INF=1e13+7;
const ll mod=2147483647;
const double EPS=1e-6;
ll n,m;
ll a[N][N],b[N][N];
int main()
{
    scanf("%lld%lld",&n,&m);
    over(i,1,n) over(j,1,m)
    {
        scanf("%lld",&a[i][j]);
        b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];//二维前缀和
    }
    ll ans=1;
    ll l=1;
    while(l<=min(n,m))
    {
        over(i,l,n)over(j,l,m)
        {
            if(b[i][j]-b[i-l][j]-b[i][j-l]+b[i-l][j-l]==l*l)
                ans=max(ans,l);
        }
        l++;
    }
    printf("%lld\n",ans);
    return 0;
}