CF755F

Windy_YY · 2023-02-01 13:50:33 · 题解

根据套路，对于每一个 i，都要从 i 到 p_i 连一条有向边。

由于 p 是一个 1\sim n 的排列，所以这张图一定是若干个环的形式。

先考虑最大化不能收到礼物的人数。

• 如果当前环的长度是 k，那么：

设每一个环上的节点是 s_i，那么为了让没有带礼物的人都能影响两个人得不到礼物，那么这种人的数量最多是 \sum calc(s_i)，其中 calc(x) 为 \lfloor \frac x 2 \rfloor。

如果上述的人数 \ge m，由于一个人最多影响两个人，所以答案是 2\times m。

否则，需要的其他的人数使用影响不到别人的人即可。

然后考虑最小化不能收到礼物的人数。

为了尽量浪费没有带礼物的人数，那么让一个环上的所有的人都忘记带礼物即可。

那么容易发现，跑一遍 01 背包，如果可以选出一些环满足这些环的长度 =m，答案是 m。

否则，只能再任意选择一段连续的环，答案为 m+1。

但是时间复杂度为 O(nm)，会超时。

对图进行观察后发现，图中可能存在多个长度相同的环，那么使用多重背包的优化即可。这样再卡卡常就可以通过这个题目啦。