A Preponderant Reunion 题解

思路

把一次操作暂时放宽为可以减去任意 $x\in[1,\min(p_i,p_{i+1})]$。放宽后的最优方案可以合并相邻的同边操作，使每次实际减去当前两数的最小值，因此最优成本不会改变。

最终的零位置必须覆盖路径上的每条相邻边。可以证明，存在最优方案使连续零段的长度只为 $1$ 或 $2$：若需要清空区间 $[l,r]$，令 $c_l=p_l$，$c_i=\max(p_i-c_{i-1},0)$，清空成本为 $\sum c_i$；把长度至少三的零段从末尾拆去两个位置不会增大成本。

做法

令 $f_i$ 表示处理到位置 $i$ 且最后一个连续零段在 $i$ 结束时的最小成本，并约定 $f_j=0$（$j\le0$）。最后的零段有两种情况：

• 只清空位置 $i$，转移为 $f_{i-2}+p_i$；
• 清空位置 $i-1,i$，转移为 $f_{i-3}+\max(p_{i-1},p_i)$。

因此

$$f_i=\min\bigl(f_{i-2}+p_i,\ f_{i-3}+\max(p_{i-1},p_i)\bigr).$$

答案为 $\min(f_{n-1},f_n)$。记录每次转移后，从右向左恢复零段，再按从左向右的顺序执行至多三次相邻操作即可完成构造。

第一档可以把二进制序列压成状态，枚举当前所有相邻的 $1$ 并搜索最少操作数。第二档中每个正数都等于 $1$，每个连续 $1$ 段从左向右两两配对即可。满档使用上述加权 DP。

特殊判断程序会模拟输出的每次操作、检查最终状态，并用同一结论的独立成本 DP 验证总代价确为全局最优。

复杂度

状态搜索为指数复杂度；二进制段贪心与满分 DP 都是 $O(n)$ 时间。满分算法使用 $O(n)$ 空间保存转移并恢复操作。