原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:最大值
1.2 题目背景、允许、禁止与限制
背景:有一个大小为 n×mn \times mn×m 的只含 0,10,10,1 两种数字的正方形
允许:选择大正方形中的一个小正方形,使得面积最大
禁止:
限制:选择出的正方形内必须0/1交替
> 0/1交替的定义是:正方形内任意两个数字(0/1)不能一样
1.3 题目数据范围与猜测
1≤n,m≤1500⟶O(n2)1 \le n,m \le 1500 \longrightarrow O(n^2)1≤n,m≤1500⟶O(n2)
1.4 一句话概括题意
在一个正方形中选择一个0/1交替的小正方形,求这个小正方形的面积最大是多少
2 题目破题推导
> 注:以下六种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维,逆向思维转正向思维
2.3 以终为始、以始为终
2.4 数学
(疑似奇偶性分析)
既然要求0/1交替,那么我们只需要关注一个大小为 2×22 \times 22×2 的正方形(因为这个大小的小正方形可以完全包含位置 (i,j)(i,j)(i,j) 的相邻点)就可以发现一个关键信息:
如果当前在网格中对应位置的编号为 111,那么这个 2×22 \times 22×2 的正方形一定是这样:
否则就是这样:
那我们很容易就可以发现:
对于一个位置 (i,j)(i,j)(i,j),(i−1,j)和(i,j−1)(i-1,j)和(i,j-1)(i−1,j)和(i,j−1) 都应是和 (i,j)(i,j)(i,j) 不同的数,而 (i−1,j−1)(i-1,j-1)(i−1,j−1) 又应是和 (i,j)(i,j)(i,j) 相同的数
2.5 手动推导
2.6 边界测试
3 模型匹配
先提取关键词:时刻求取当前最大值、只和特定的几位有关系
那不用说了,一定是 动态规划\huge{动态规划}动态规划
4 具体方案
4.1 动态规划定义(重点)
首先,先建立 dp 数组
设置 dpij{dp_i}_jdpi j 表示以 (i,j)(i,j)(i,j) 为右下角时,符合条件正方形的最大面积
但是出现了问题,我们无法确定当前考虑的这一项是否符合条件(第一部分有讲),因此考虑扩维
定义 dpijk(0≤k≤1){{dp_i}_j}_k(0 \le k \le 1)dpi j k (0≤k≤1) 表示以 (i,j)(i,j)(i,j) 为右下角并且当前这个位置的数字是 kkk 时,符合条件正方形的最大面积
4.2 初始化
求最大值,所以dp数组每一项都设为小值
4.3 状态转移方程
我们的定义清晰了,合法方案也清晰了,因此直接就是(懒得打latex数学公式了)
4.4 答案求取
由于所有位置都有可能作为最大交替正方形的右下角,因此都要遍历每一项
并且每一项 dpij0{{dp_i}_j}_0dpi j 0 dpij1{{dp_i}_j}_1dpi j 1 都考虑
(其实不考虑也没关系,因为不会更新的那一项一直都是小值,不会参与到最终答案)
5 最终代码(禁止抄袭,仅用于参考)