(1) CF1684D Traps
有 \(n\) 个数字 \(a_1 \sim a_n\) 排成一排，你需要从左到右依次越过所有数。
两种越过 \(i\) 的方式：
- 花费 \(a_i\) 的代价越过；
- 花费 \(0\) 的代价越过，后面的 \(a_i\) 都加 \(1\)。
现在你拥有最多 \(k\) 次操作二的机会，求最小的代价总和。
一定会使用 \(k\) 次操作二。否则可以在最后一个使用操作一的位置改用操作二，使答案更优。
假设这 \(k\) 次操作二的地方为 \(i_1, i_2, \dots, i_k\)，我们考虑其中一个位置 \(i_j\) 的收益（收益指在 \(i_j\) 位置由操作一改为操作二后答案会变小多少）：
- 本身的代价 \(a_{i_j}\) 变成了 \(0\)，收益增加 \(a_{i_j}\)。
- 位置 \(i_j + 1 \sim n\) 中，除了位置 \(i_{j + 1}, i_{j + 2}, \dots, i_{k}\)，代价都会加一（因为它们在跳跃时代价都是 \(0\)），收益减少 \(n - i_j - (k - j)\)。
综上，总收益为：
\[\sum_{j=1}^k (a_{i_j} - n + i_j + k - j) \]整理得：
\[-nk + k^2 - \frac{k(k+1)}2 + \sum_{j=1}^k(a_{i_j} + i_j) \]显然我们希望让收益越大越好，所以我们得目标是最大化这个式子的值。
其中 \(-nk + k^2 - \frac{k(k+1)}2\) 为定值，我们希望最大化 \(\sum_{j=1}^k(a_{i_j} + i_j)\)。所以我们将所有值按照 \(a_i + i\) 排序并取前 \(k\) 大即可。
(2) CF1029E Tree with Small Distances
给定一颗 \(n\) 个节点的树，以 \(1\) 为根。
求最少在树中加几条边，使得任意一点到 \(1\) 的距离均小于等于 \(2\)。
不难发现最优策略中，每条加的边都有端点 \(1\)。
第一步，最自然的想法就是将 \(1\) 和最深的叶节点连边。其实不然，最优的策略是连接 \(1\) 和叶子节点的父亲。这样能把这个叶子节点的所有兄弟和它父亲的父亲都管控到。
接下来上一步的点就不需要考虑了。我们要做的仍然是连接 \(1\) 和最深的点的父亲。如此迭代即可。
实现上，我们可以维护大根堆，以节点的深度从大到小排序。每次取出堆顶即可。
(3) CF1197C Array Splitting
给出一个长度为 \(n\) 的严格单调增的序列，将其分成 \(k\) 段，使得每一段的极差的和最小，求这个最小的和。
推式子。
若这 \(k\) 段分别为 \([i_1, i_2 - 1], [i_2, i_3 - 1], \dots, [i_k, i_{k + 1} - 1]\)，其中 \(i_1 = 1, i_{k + 1} = n + 1\)。那么极差和为：
\[a_{i_2 - 1} - a_{i_1} + a_{i_3 - 1} - a_{i_2} + a_{i_4 - 1} - a_{i_3} + \dots + a_{i_{k + 1} - 1} - a_{i_k} \]整理一下，把 \(+a_{i_j - 1}\) 和 \(-a_{i_j}\) 放在一起：
\[-a_{i_1} + a_{i_{k+1} - 1} + (a_{i_2 - 1} - a_{i_2}) + (a_{i_3 - 1} - a_{i_3}) + \dots + (a_{i_k - 1} - a_{i_k}) \]其中 \(-a_{i_1} + a_{i_{k+1} - 1}\) 即 \(a_n - a_1\) 是一定的。我们希望让这个式子的值最小，就意味着我们要最小化 \((a_{i_2 - 1} - a_{i_2}) + (a_{i_3 - 1} - a_{i_3}) + \dots + (a_{i_k - 1} - a_{i_k})\)。因此求 \(d_i = a_{i - 1} - a_i\) 的前 \(k - 1\) 小即可。
(3) CF1038D Slime
给定 \(n\) 个数 \(a_i\)。每次可以选择两个相邻的 \(a_i, a_{i + 1}\) 将其合并为 \(a_i - a_{i + 1}\) 或 \(a_{i + 1} - a_i\)。求 \(n - 1\) 次操作后的数的最大值。
多手玩几组可以发现，最终的答案一定是对每个 \(a_i\) 乘上 \(\pm 1\) 的系数后求和。因为题目的操作为 \(a_i - a_{i + 1}\) 或 \(a_{i + 1} - a_i\)，也就是将相邻两个数分别乘上 \(\pm 1\)。
所以我们可以对于每个负数乘 \(-1\) 变成正数，正数乘 \(1\) 保持正数，再求和即为答案。其实就是每个数的绝对值之和。
注意会有一个问题。将每个 \(a_i\) 乘 \(\pm 1\) 的过程中，不能做到将所有 \(a_i\) 全部乘相同的系数。所以在所有 \(a_i\) 同号时贪心选择某个数乘另外一个系数即可。
(4) CF804A Find Amir
有一张 \(n\) 个节点的完全图，其中连接 \(i, j\) 两点的边的边权为 \((i + j) \bmod (n + 1)\)。求走完所有城市所需的最小花费（起点任选）。
方案是 \(1 \to n \to 2 \to (n - 1) \to 3 \to \dots\)，边权分别为 \(0, 1, 0, 1, \dots\)。
所以答案为边数的一半，即 \(\left \lfloor \dfrac {n-1}2 \right \rfloor\)。
标签：24,03,19,sum,dots,操作,代价,节点,pm From： https://www.cnblogs.com/2huk/p/18087817