Problem

给定一个长度 $n$ 的整数序列 $A$ 现选取 $m$ 个点，使得这些点两两不相连，求最大和 (最小同理)

Solution

以最大值为例

策略：若当前状态最大值不选，则一定选择最大值左右两点

归纳法证明：

1. $m = 1$ ， 选取最大值
2. $m = 2$ ， 选取最大值和不相邻的次大值，或者选择最大值两侧的点

得证

算法流程如下：

1. 建立一个大根堆，依次插入所有数
2. 每次取出最大值，加入答案。记最大值下标为 $i$ ， 修改 $A_i$ 为 $A_{lc(i)} + A_{rc(i)} - A_i$ ， 并且加入堆，删除$lc(i)$ 和 $rc(i)$。其中 $lc(i) 和 rc(i)$ 为链表，初始分别指向 $i-1$ 和 $i+1$
3. 重复 $m$ 次操作2

例题

[APIO/CTSC 2007]

hint

选相邻一定最优

---

生日礼物

hint

将所有正数和负数合并(0需要被忽略)

现选择所有正数段，记为 $p$ 个，若 $p \leq m$ ，则直接输出，否则尝试删除 $p-m$ 个正数

1. 删除最小的正数，堆中加入该正数和左右两数的和，方便下次转移
2. 合并两个正数，减去中间的数(绝对值)，向堆中加入合并值

综上，选不相邻一定最优

注意：边界负数不选

---