P5917 题解

Helenty · 2025-08-19 18:00:47 · 题解

不是很简单的绿题。

需要有一定思考的 DFS 题。

给每一种布局的 4 个矩形进行编号，暴力枚举每个位置放哪个矩形，包括横着放，即原来的 a 和 b，以及竖着放，即长和宽倒过来的 b 和 a。

枚举好之后，计算各种布局的长和宽，根据长和宽计算面积，如果面积是最小值，那么标记一下 f_0 和 f_i 为最小面积，已确定最小面积以及面积最小时长/宽是 i。

计算面积，需要分类讨论：

• 布局 1：长是 4 个矩形的长之和；宽是 4 个矩形的宽的最大值。

• 布局 2：长是前 3 个矩形长之和跟第 4 个矩形长的最大值；宽是前 3 个矩形的宽的最大值加上第 4 个矩形的宽。

• 布局 3：（从左到右编号，下面横着的是 4 号）长是第 4 个的长加上左边的最大值；宽是左右两边宽的最大值，左边还要嵌套求最大值。

• 布局 4 和 5：上下两个编号成 3 和 4，那么放中间还是左边结果是相同的，求法类似。

• 布局 6：规定上面两个的长要比下面两个的小，因为如果大的话，就是旋转，也会求到的，限制了之后后面更好分类讨论。

首先编号，右下角为 1 号，顺时针依次编号，宽肯定是左边宽和右边宽的最大值，上面两个不会给顶上去，因为不够长；

接着是长，至少是下面两个的长之和，但中间可能有空隙，如 3 比 2 长且 1 比 2 要宽、4 比 1 长且 2 比 1 要宽。

然后写出代码就可以了。