P1387 最大正方形

第九题 P1387 最大正方形

题目分析

设 \(dp_{i,j}\) 表示以 \(i,j\) 为右下角的最大正方形的边长。

状态转移方程为:

\(dp_{i,j} = \min(dp_{i,j-1},dp_{i-1,j},dp_{i-1,j-1})+1\)

为什么取最大边长却要用 \(\min\) 来转移呢？

因为在三者中取最小，等于另外两者一定大于最小的值，不需要考虑另外两者比边长小的问题。且以最小的值 \(+1\) 为边长进行状态转移，一定会形成为以 \(i,j\) 为右下角的最大正方形，再大一点都不符合条件，不会形成正方形。

code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,dp[105][105],a[105][105],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]) dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

\(2023.1.29\)