自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:34:45，当前版本为作者最后更新于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