P7967 题解

EuphoricStar · 2022-01-09 09:16:18 · 题解

思路

dp。

先将所有磁铁按 r_i 从小到大排序，然后令 f_{i,j,k} 表示考虑了前 i 个磁铁，分为 j 组，占用的空位数为 k 的方案数。

那么我们有三个转移：

第 i 个磁铁单独成为了一个新组：f_{i,j,k} \to f_{i-1,j-1,k-1}。
第 i 个磁铁接在前面 j 个组的端点：f_{i,j,k} \to f_{i,j,k} + f_{i-1,j,k-a_i} \times j \times 2（k \ge a_i）
第 i 个磁铁连接前面 j+1 个组的两个：f_{i,j,k} \to f_{i,j,k} + f_{i-1,j+1,k-2 \times a_i+1} \times j \times (j+1)（k \ge 2 \times a_i - 1）。

最后我们得到了所有磁铁分为 1 组长度为 i 的方案数，那么它对答案的贡献为 f_{n,1,i} \times \binom{l-i+n}{n}（根据插板法易得）。

那么这题就做完了，时间复杂度 O(n^2 \times l)。

code