题解：CF1775F Laboratory on Pluto

Abczzzzz · 2026-04-24 09:16:02 · 题解

显然如果图形有凹肯定不优，所以周长就是包围它的长方形的周长。设长方形的周长为 2x，则长方形长加宽为 x，这个长方形可以取得的最大面积为 \lfloor\frac{x}{2}\rfloor\times\lceil\frac{x}{2}\rceil，于是第一问就做完了。

最优的 x 通过枚举固定下来之后，就可以枚举所有的 h+w=x 使得 h\times w \ge n。考虑对这种图形计数，发现第一行、最后一行、第一列、最后一列一定都有至少一个元素，要不然可以缩进去更优。于是扣掉的四个角就独立了，独立计算是好算的，直接 DP，不讲了。拼起来的时候，由于空格总数一定小于短边长度（否则不优），所以拼起来的时候就不需要格外判了，一定不会接触。