P1387 最大正方形

DP
1.状态定义：

f[i][j]: 以（i，j）为右下角，可构造的最大正方形的边长

2.状态计算

想一想以(i,j)为右下角的正方形，有哪一个状态转移过来

对于已经确定的点：f[i][j] = x 表示包含（i，j),向上连续x个节点，向左连续x个节点

对于待确定的点：f[i][j] = x，需要考虑f[i-1][j],f[i][j-1],f[i-1][j-1] 中取 min.

最后

答案取所有极大正方形中取最长的边长

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int n,m;
int a[N][N];
int f[N][N];

int main(){
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
		
		if(a[i][j]==1)
		f[i][j]=min( min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans = max(ans,f[i][j]);
		}
	}
	cout<<ans;
	return 0;
}

悬线法

对于一个很大的测试数据，用悬线法

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int n,m;
bool a[N][N];
int l[N][N],r[N][N],up[N][N];
int ans;

int main() {

	scanf("%d%d",&n,&m);
    
	//初始化
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
		    bool op;
		    cin>>op;
		    if(op) a[i][j] = 1;
			l[i][j] = j;
			r[i][j] = j;
			up[i][j] = 1;
		}
	}

	//延申每一个点的左端点
	for(int i=1; i<=n; i++) {
		for(int j=2; j<=m; j++) {
			if(a[i][j] && a[i][j-1]) {
				l[i][j] = l[i][j-1];
			}
		}
	}

	//延申每一个点的右端点
	for(int i=1; i<=n; i++) {
		for(int j=m-1; j>0; j--) {
			if(a[i][j] && a[i][j+1]) {
				r[i][j] = r[i][j+1];
			}
		}
	}

	//向上最高的矩形，所能达到的宽度
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(a[i][j] && a[i-1][j]) {
				up[i][j] = up[i-1][j] + 1;
				l[i][j] = max(l[i-1][j],l[i][j]);
				r[i][j] = min(r[i-1][j],r[i][j]);
			}
			int a = r[i][j] - l[i][j] + 1;  //宽度 
			int b = min(a,up[i][j]);   //取更小的-正方形
			ans = max(b,ans) ;
		}
	}
	printf("%d",ans);
	return 0;
}