题解：P17224 [Math×Girl²] 搬家

nnh915 · 2026-08-10 19:09:49 · 题解

本题解可能用到如下 2 个公式：

设恰好有 i 个体积为1的物品的方案数为 f_i。其中 f_0=f_n=1，考虑如何求 f_i。

当 i=1 时，分 m 的奇偶性讨论。若 m 为奇数则为 n，否则为 \min(\lfloor \frac{m}{2} \rfloor, n)。

当 i\ge2 时：

• 若能将物品全部选完，即 i+2\times (n-i) \le m，则无限制。

• 否则，分类讨论 i 与 m 的大小关系：

  • 若 i \ge m，则只会选体积为 1 的物品。设第一件体积为 2 的是第 p 个物品，若该物品的价值大于最小的 2 个 被选的体积为 1 的物品，则不为最优解；反之定为最优解。简单分析得知要求 p \ge m，即要求前 m-1 个物体体积必为 1。方案数为 \binom{n-m+1}{i-m+1}。
  • 否则，设 t = \lfloor \frac{M-i}{2} \rfloor再分类讨论 m 与 i 的奇偶性：
  • 若 m 与 i 同奇偶，打包机装满 i 个 1，t 个 2 物品。此时要求第一个未被装入的 2 的价值 \le 最后两个被装入的 1 的价值之和，即第一个未被装入的 2 的编号 \ge  倒数第二个被装入的 1 的编号。枚举第 i-1 个 1 在位置 j，则要求 1 \sim (i-1) 位恰有 i-2 个 1，最后 1 个 1 在 (j+1) \sim n 内。记 lim = \min(n-1,i+t-1)，故方案数为 \sum_{j=i-1}^{lim} \binom{j-1}{i-2}\times(n-j) = (n-i+1) \times \binom{lim}{i-1} - (i-1) \times \binom{lim}{i}。
  • 若 m 与 i 异奇偶，此时要求第一个未被装入的 2 的价值 \le 最后两个被装入的 1 的价值之和，即第一个未被装入的 2 的编号 \ge 最后一个被装入的 1 的编号。枚举第 i 个 1 在位置 j，则方案数为 \sum_{j=i}^{\min(n,i+t)}\binom{j-1}{i-1} = \binom{\min(n,i+t)}{i}。