http://www.zybbs.org/JudgeOnline/problem.php?id=1057

这个模板题老不做又忘了怎么做了……于是写了下，结果居然花了一个半小时……不断绕晕……我真是太水了……

以前做这类题的时候用的是自己的YY法（YY法的时间复杂度好像不对的？我现在连YY法都不会了）……现在专门学了王知昆神犇所说的“悬线法”……他说的非常清楚，ym一下！（不过这题是在格子里，要稍微改一下）

枚举每个点，记录向上的“悬线”长度（到第一个不能延伸处的长度），和这条悬线向左/向右最多能延伸到哪里。这些东西都可以用DP推出来。然后这就是一个极大子矩阵。而正方形必定也卡在某个极大子矩阵中。

时间复杂度是O(nm)的！

#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n,m,l[2][2000],r[2][2000],h[2][2000],a1,a2;
_Bool v[2][2000],c;
char str[8010000],*p=str;
main(){
	int i=-1,j;
	for(scanf("%d%d",&n,&m),fread(p,1,8010000,stdin);++i!=n;c=!c){
		for(j=-1;++j!=m;l[c][j]=j&&v[c][j]!=v[c][j-1]?l[c][j-1]:j){
			while(*++p!=48&&*p!=49);v[c][j]=*p==49;
			h[c][j]=i&&v[c][j]!=v[!c][j]?h[!c][j]+1:1;
		}for(j=m;j--;r[c][j]=j!=m-1&&v[c][j]!=v[c][j+1]?r[c][j+1]:j)if(i&&v[c][j]!=v[!c][j])l[c][j]=max(l[c][j],l[!c][j]);
		for(j=m;j--;a1=max(a1,min(h[c][j],r[c][j]-l[c][j]+1)),a2=max(a2,h[c][j]*(r[c][j]-l[c][j]+1)))if(i&&v[c][j]!=v[!c][j])r[c][j]=min(r[c][j],r[!c][j]);
	}printf("%d\n%d\n",a1*a1,a2);
	return 0;
}

• inline
• block