洛谷 [P1387] 最大正方形

时间:2022-09-20 18:42:46

本题非常有趣。
(n^6) 枚举四个端点,每次遍历矩阵求解。
(n^4) 先处理前缀和,枚举四个端点,每次比较前缀和和正方形面积。
(n^3) 枚举左上方端点,在枚举边长,前缀和优化
(n^2logn) 枚举左上方端点,发现条件是单调的,于是二分边长
(n^2) DP做法,枚举右下端点,若该点是0,dp[i][j]=0;若该点是1,dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
可以在读入的时候直接处理

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return rv*fh;
}
int n,m,dp[105][105],ans;
int main(){
freopen("in.txt","r",stdin);
n=init();m=init();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int t=init();
if(!t) dp[i][j]=0;
else dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
fclose(stdin);
return 0;
}