题目理解

我们有一个 $N \times M$ 的矩形建筑物，需要将其划分为若干个矩形公寓，满足：

1. 每个公寓都是整数尺寸的矩形
2. 所有公寓完全覆盖建筑物且互不重叠
3. 每个公寓必须接触到建筑物的边界
4. 每个公寓有期望面积 $K$，偏差定义为 $(实际面积 - K)^2$
5. 目标是最小化所有公寓的偏差之和

关键观察

1. 边界接触约束的重要性

"每个公寓必须接触到建筑物的边界"这一约束非常关键。这意味着：

• 不能有完全被其他公寓包围的"内部"公寓
• 划分必须从边界开始向内延伸
• 这大大限制了可能的划分方式

2. 划分的结构分析

由于所有公寓都要接触边界，整个划分可以看作是从边界开始的一系列切割。具体来说：

• 我们可以水平或垂直地切割矩形
• 每次切割都会产生新的矩形，这些新矩形自然接触边界
• 最终所有子矩形都满足边界接触条件

3. 动态规划状态设计

设 $dp[x][y]$ 表示划分一个 $x \times y$ 的矩形（从原建筑的某个角开始）的最小偏差和。

但是这样不够，因为我们需要知道当前矩形在原始建筑中的位置，以确保所有子矩形都接触边界。

更好的状态设计： $dp[x][y][a][b][c][d]$ 表示划分一个 $x \times y$ 的矩形，且该矩形的四条边是否接触原始建筑边界的的最小偏差值。其中 $a,b,c,d$ 分别表示上、下、左、右边界是否接触原始建筑边界。

算法设计

1. 状态定义

令 $dp[x][y][mask]$ 表示：

• $x$: 当前矩形的宽度
• $y$: 当前矩形的高度
• $mask$: 4位二进制数，表示四条边是否接触原始建筑边界

例如：$mask = 1111$ 表示当前矩形的四条边都接触原始建筑边界（即整个建筑本身）。

2. 状态转移

对于当前矩形，我们有两种选择：

选择1：不继续划分 如果当前矩形作为一个完整的公寓，偏差为 $(x \times y - K)^2$。

选择2：进行划分 我们可以选择水平或垂直切割：

• 水平切割：在位置 $i$ ($1 \leq i < y$) 处切割，将矩形分为上下两部分
• 垂直切割：在位置 $j$ ($1 \leq j < x$) 处切割，将矩形分为左右两部分

切割后，我们需要更新子矩形的边界接触信息：

• 对于上半部分：下边界不再接触原始边界（因为被切割了）
• 对于下半部分：上边界不再接触原始边界
• 左右部分同理

3. 边界条件

• 当 $x = 0$ 或 $y = 0$ 时，偏差为0（空矩形）
• 当矩形太小无法划分时，只能作为单个公寓

4. 记忆化搜索实现

由于状态空间较大，使用记忆化搜索比迭代DP更合适：

1. 定义递归函数 solve(x, y, mask)
2. 如果该状态已计算过，直接返回结果
3. 否则：
   • 计算不划分的代价
   • 枚举所有可能的切割位置，计算划分后的总代价
   • 取最小值作为该状态的结果

复杂度分析

状态数量

• $x$: 0 到 $N$，约300
• $y$: 0 到 $M$，约300
• $mask$: 0 到 15（4位二进制）
• 总状态数：$300 \times 300 \times 16 \approx 1.44 \times 10^6$

状态转移

每个状态需要枚举：

• 水平切割：$O(M)$ 种可能
• 垂直切割：$O(N)$ 种可能

总复杂度：$O(N \times M \times 16 \times (N + M)) \approx 300^2 \times 16 \times 600 \approx 8.64 \times 10^8$

这个复杂度较高，需要优化。

优化策略

1. 预处理面积偏差

预先计算所有可能尺寸的矩形的偏差值，避免重复计算。

2. 切割位置优化

• 不需要枚举所有切割位置，可以只枚举有意义的切割
• 利用四边形不等式等优化技巧

3. 状态剪枝

• 如果当前矩形已经很小，直接返回不划分的代价
• 如果当前偏差已经很大，可以提前剪枝

4. 循环顺序优化

合理安排计算顺序，利用缓存局部性。

正确性分析

1. 边界接触约束的保证

通过 $mask$ 参数，我们精确跟踪了每个子矩形与原始边界的接触情况，确保最终所有公寓都满足边界接触条件。

2. 最优子结构

问题的确具有最优子结构性质：整个矩形的最优划分必然由子矩形的最优划分组成。

3. 无后效性

每个子矩形的划分只依赖于其尺寸和边界接触情况，与外部划分方式无关。

特殊情况处理

1. 期望面积等于实际面积

当 $x \times y = K$ 时，偏差为0，这是最优情况。

2. 无法完美划分

如样例1中 $3 \times 3 = 9$，期望面积 $K=2$，无法得到偏差为0的划分。

3. 小矩形情况

当矩形尺寸小于期望面积时，偏差计算仍然有效。

总结

这道题的核心在于通过精细的状态设计来处理复杂的几何约束：

1. 状态设计：使用 $mask$ 参数跟踪边界接触信息
2. 划分策略：通过水平垂直切割生成所有合法划分
3. 动态规划：利用最优子结构性质递推求解
4. 优化技巧：预处理、剪枝等降低复杂度

这种"状态压缩 + 记忆化搜索"的方法在解决带复杂约束的划分问题时非常有效，特别是当约束可以转化为状态参数时。题目虽然看似简单，但边界接触约束使得问题变得相当复杂，需要仔细的状态设计和优化。