P12105 [NWRRC2024] Another Brick in the Wall 题解
违规用户名1045961
·
·
题解
注意到题目里面的这幅图。
可以发现，每行都在最左或最右放了一个 1\times 3 砖头，并且不能放得更少。不难想到当 l 为奇数时答案就是 h，因为如果这样放，一行长度就是 3+2k(k\in\Z)，一定为奇数。
当 l 为偶数时，可以想几个例子。
不难发现，l 为偶数时最佳方案是 2 个 1\times3 砖头加上 \frac{l-6}2 个 1\times2 砖头和 \frac{l}2 个 1\times2 砖头交替。要让 1\times3 砖头使用得尽量少就要使“2 个 1\times3 砖头加上 \frac{l-6}2 个 1\times2 砖头”的一行尽量少，这样的一行有 \lfloor\frac{h}2\rfloor 个。答案就是 \lfloor\frac{h}2\rfloor\times2。