题解

思路

状态含义

在尚未合并的数组中，相邻两个数相等就能少保留一个元素。因此等价地，我们要最大化 $2n-1$ 个相邻边界中“左右相等”的数量。

处理完 $a_i$ 后，只需关心当前最后一个拆分值。若它为 $x$，下一项 $a_{i+1}$ 选择左半部分为 $x$ 时可以合并跨项边界；若 $a_i$ 为偶数并拆成两个 $a_i/2$，还可以合并项内边界。

做法

子任务 1：完整枚举

枚举每个 $a_i$ 的左半部分 $1,2,\ldots,a_i-1$，构造长度 $2n$ 的数组并直接统计连续段数。复杂度为

子任务 2：显式端点 DP

令 $f_i(y)$ 表示处理前 $i$ 项、且第 $i$ 项右半部分为 $y$ 时的最小合并后长度。令 $x=a_i-y$，则

设上一层最小值为 $m$，花费部分等于 $\min(m+1,f_{i-1}(x))$。所以每层只需扫描所有 $1\le y<a_i$，复杂度 $O(nV)$，其中 $V=\max a_i$。

满分算法：隐式维护最优端点集合

改为最大化已经消去的边界数，并只维护达到当前最优值的所有可能右端点。设这个集合为 $S$，处理新数 $v$：

1. 先删去 $S$ 中不小于 $v$ 的值，因为左半部分必须为正数。
2. 若 $v$ 为偶数且 $v/2\in S$，可以同时消去跨项边界和项内边界，收益增加 $2$，新端点只能是 $v/2$。
3. 否则若 $S$ 非空，至少可以消去跨项边界，收益增加 $1$；原端点 $x$ 变为新右端点 $v-x$。当 $v$ 为偶数时，也可以只消去项内边界，因此再加入孤立点 $v/2$。
4. 若 $S$ 为空，无法消去跨项边界。偶数 $v$ 可以消去项内边界并把集合设为 $\{v/2\}$；奇数 $v$ 没有收益，任意 $1\le x<v$ 都可作为新端点。

集合始终是一个整数区间与若干孤立点的并。变换 $x\mapsto v-x$ 是仿射翻转；用两个参数记录当前坐标系，并用有序集合维护孤立点，就能在总计 $O(n\log n)$ 时间、$O(n)$ 空间内完成所有删除、查询、插入和翻转。

设最多消去 saved 个边界，答案为 $2n-\text{saved}$。

正确性说明

显式 DP 的转移枚举了新拆分的全部右端点，并完整区分跨项与项内两个边界，故它给出最优值。满分算法维护的集合恰是显式 DP 中达到全局最优值的端点：四种更新分别对应“两个边界都合并”“只合并跨项边界”“只合并项内边界”和“均不合并”。若两个边界都能合并，其收益严格最大；否则能合并任意一个边界就不会劣于均不合并。因此按上述贪心保留的恰好是下一层所有最优状态。归纳可知最终 saved 最大，输出最小长度正确。

复杂度

子任务 1 为 $O\!\left(n\prod(a_i-1)\right)$；子任务 2 为 $O(nV)$；满分算法对每个孤立端点至多插入、删除常数次，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。多组数据时把 $n$ 替换为所有数据的长度总和。