题解：P11686 [JOIGST 2024] 相聚 / いっしょ

ELECTRODE_kaf · 2025-02-09 15:10:06 · 题解

首先贪心。最佳方案中，将原本不在同一位置的多于 3 只河狸移动到一起相比将其两两分组（奇数个则保留一组 3 只）肯定不优，所以只需要考虑一组 2 只或一组 3 只。

其次 DP。将 a_i 升序排列。设 dp_i 表示考虑前 i 只的最小花费，则 dp_1=+\infty,dp_2=a_2-a_1,dp_3=a_3-a_1,dp_i = \min(dp_{i - 2} + (a_i - a_{i - 1}), dp_{i - 3} + (a_i - a_{i - 2}))。