洛谷 P1681 分析（别看）

科技起源

2026-07-07 08:09:25

发布于：河北

5阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：最大值

1.2 题目背景、允许、禁止与限制

背景：有一个大小为 $n \times m$ 的只含 $0,1$ 两种数字的正方形
允许：选择大正方形中的一个小正方形，使得面积最大
禁止：
限制：选择出的正方形内必须0/1交替

0/1交替的定义是：正方形内任意两个数字（0/1）不能一样

1.3 题目数据范围与猜测

$1 \le n,m \le 1500 \longrightarrow O(n^2)$

1.4 一句话概括题意

在一个正方形中选择一个0/1交替的小正方形，求这个小正方形的面积最大是多少

2 题目破题推导

注：以下六种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

2.4 数学

（疑似奇偶性分析）
既然要求0/1交替，那么我们只需要关注一个大小为 $2 \times 2$ 的正方形（因为这个大小的小正方形可以完全包含位置 $(i,j)$ 的相邻点）就可以发现一个关键信息：
如果当前在网格中对应位置的编号为 $1$ ，那么这个 $2 \times 2$ 的正方形一定是这样：

否则就是这样：

那我们很容易就可以发现：
对于一个位置 $(i,j)$ ， $(i-1,j)和(i,j-1)$ 都应是和 $(i,j)$ 不同的数，而 $(i-1,j-1)$ 又应是和 $(i,j)$ 相同的数

2.5 手动推导

2.6 边界测试

3 模型匹配

先提取关键词：时刻求取当前最大值、只和特定的几位有关系
那不用说了，一定是 $\huge{动态规划}$

4 具体方案

4.1 动态规划定义（重点）

首先，先建立 dp 数组
设置 ${dp_i}_j$ 表示以 $(i,j)$ 为右下角时，符合条件正方形的最大面积
但是出现了问题，我们无法确定当前考虑的这一项是否符合条件（第一部分有讲），因此考虑扩维
定义 ${{dp_i}_j}_k(0 \le k \le 1)$ 表示以 $(i,j)$ 为右下角并且当前这个位置的数字是 $k$ 时，符合条件正方形的最大面积

4.2 初始化

求最大值，所以dp数组每一项都设为小值

4.3 状态转移方程

我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）

for (int i = 1;i <= n;i++){
	for (int j = 1;j <= m;j++){
		if (a[i][j] == 0){
			dp[i][j][0] = min({dp[i - 1][j][1], dp[i][j - 1][1], dp[i - 1][j - 1][0]}) + 1;
		}
		if (a[i][j] == 1){
			dp[i][j][1] = min({dp[i - 1][j][0], dp[i][j - 1][0], dp[i - 1][j - 1][1]}) + 1;
		}
	}
}

4.4 答案求取

由于所有位置都有可能作为最大交替正方形的右下角，因此都要遍历每一项
并且每一项 ${{dp_i}_j}_0$ ${{dp_i}_j}_1$ 都考虑
~~（其实不考虑也没关系，因为不会更新的那一项一直都是小值，不会参与到最终答案）~~

5 最终代码（禁止抄袭，仅用于参考）

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

int n, m;
const int N = 1555;
int a[N][N];
int dp[N][N][2];

int main(){
	
	memset(dp, 0, sizeof(dp));
	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] == 0){
				dp[i][j][0] = min({dp[i - 1][j][1], dp[i][j - 1][1], dp[i - 1][j - 1][0]}) + 1;
			}
			if (a[i][j] == 1){
				dp[i][j][1] = min({dp[i - 1][j][0], dp[i][j - 1][0], dp[i - 1][j - 1][1]}) + 1;
			}
		}
	}
	int mx = INT_MIN;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= m;j++){
			mx = max({mx, dp[i][j][0], dp[i][j][1]});
		}
	}
	cout << mx;
	
	return 0;
}