P7967 Magneti 题解

题目相当于要求放置磁铁的方案数，使得相邻两个磁铁的间隔不小于 。

我会状压！用 记录每个磁铁是否放过，从左往右计算。然而这个题目 ，状压并不足以通过。

我们发现状压的问题在于我们知道放了哪些磁铁防止重复放置。我们可以考虑将磁铁按照一定顺序放置，但是这样就不能从左到右转移了，因为磁铁可能是乱序的。

不妨将磁铁按照从大到小排序，这样我们只需要在放下磁铁的时候考虑限制即可。此时在位置 放下一个 的磁铁就意味着 这部分区间不能再放磁铁了，由于我们已经排序好了，因此之后所有磁铁的区间要么都在这个磁铁左侧，要么在右侧。相当于是将整个序列切成了两段。

这启示我们可以用一小段来重新拼出来整个序列，在状态中维护这些小段的信息（“连续段 dp”）。

考虑转移有哪些可能：

• 新开一段。
  • 此时段数会增加 。长度会增加 。如果不在开头/结尾，还会额外增加 。
  • 此时只有 种选择的方案（小段之间没有顺序）。
• 将两段粘在一起。
  • 此时段数会减少 ，长度会增加 。
  • 有 种选择方式（ 表示段数），如果有作为开头/结尾的段需要减去。
• 附加在前面/后面。
  • 段数不变，长度会增加 。不在开头/结尾会额外增加 。
  • 有 种方式，需要注意开头的段不能附加在前面，结尾的段同理，这部分分需要减去。

我们发现需要记录段数，总长度和是否有作为开头/结尾的段。因此我们把这些都加入到状态里面。

转移是容易的。复杂度 。

如果剩下了一些空的格子（假设有 个），我们把它们插入到原来的序列中。一共 个磁铁将序列分成了 段，每个格子具体被插入到两个磁铁间的哪个位置并不重要。因此插板法一下就可以得到是 。

但是这样常数并不优秀，而且也很难写。

有没有更加优秀的做法？

我们发现上面做法的问题在于加入磁铁的时候在开头/结尾对于长度的影响不一样。目前的加入顺序无法避免这个问题。因此我们考虑从小到大加入，这样我们就只需要考虑当前的半径就行。

依旧是这三种转移：

• 新开一段。
  • 此时段数会增加 。长度会增加 。
  • 此时只有 种选择的方案（小段之间没有顺序）。
• 将两段粘在一起。
  • 此时段数会减少 ，长度会增加 。
  • 有 种选择方式（ 表示段数）。
• 附加在前面/后面。
  • 段数不变，长度会增加 。
  • 有 种方式。

复杂度 。