训练
7 月没有做题题题题题题题题题。
MdOI R5 Many Minimizations
原问题有个经典做法，首先考虑暴力 DP，\(f_{i,j}\) 表示第 \(i\) 个数 \(=j\) 的最小代价，不难发现 DP 值是个分段函数，然后考虑用堆来维护。
设 \(mn_i=\min_{j}\{f_{i,j}\}\)，每次操作相当于是往堆中先加入两个 \(a_i\)，然后弹出最大值 \(mx\)，可以发现 \(mn_i=mn_{i-1}+mx-a_i\)。
于是，我们发现当 \(a_i<mx\) 时才会有贡献。计算答案时，我们对每个 \(a_i\le t< mx\) 分开计算，不难发现，\(t\) 的个数 \(= mx-a_i\)。
我们把 \(a_i< x\) 的设为 \(0\)，将 \(a_i\ge x\) 的设为 \(1\)，则就相当于是一个函数 \(g_i\) 表示堆内 \(1\) 的个数。
-
当 \(0\) 加入时：
- 若 \(g_{i-1}>0\)，则答案增加 \(1\)；
- 若 \(g_{i-1}=0\)，则答案不变。
换而言之，\(g_{i}=\max(0,g_{i-1}-1)\).
-
当 \(1\) 加入时：
\(g_{i}=g_{i-1}+1\)。
我们发现对 \(0\) 取 \(\max\) 的操作，是我们比较难处理的。
我们把 \((i,g_i)\) 看成一个点。我们考虑将对 \(0\) 取 \(\max\) 的位置都先整体向上平移，并要求平移后的路径至少有一个点在 \(x\) 轴上，这个限制我们可以通过 \(y\) 坐标全部 \(\ge 0\) 的方案数减去 \(y\) 坐标全部 \(\ge 1\) 的方案数来处理，计算后面的东西可以使用反射容斥来算。
对于 \((0,a)\) 出发，到 \((n,b)\) 结束的路径，我们考虑计算它对答案。首先，总的下降次数为 \(\frac{n+a-b}{2}\)，而由于对 \(0\) 取 \(\max\) 的位置不对答案产生贡献，所以贡献为 \(\frac{n+a-b}{2}-a=\frac{n-a-b}{2}\)。
时间复杂度 \(O(n^2)\)。
记录。