题解：P14367 [JOISC 2018] 帐篷 / Tents

qejwdi · 2026-01-25 20:56:29 · 题解

我为什么不会做啊。难点是想到这个题是 dp。

令 f_{i,j} 表示 i 行 j 列的答案。

考虑第 i 行怎么放：

• 如果不放就是 f_{i-1,j}。
• 如果选一列没放过的放就是 f_{i-1,j-1} \times 4j。
• 如果选一列放过的就是 f_{i-2,j-1} \times j。
• 如果选两列就是 f_{i-1,j-2} \times \binom{j}{2}。

然后就做完了。