重操旧业。
agc049e Increment Decrement
对于一个非负整数序列，我们可以做两个操作：
- 选定一项令其加一或减一，代价为 \(1\) 。
- 选定一个区间令其中每一项同时加一或同时减一，代价为 \(C\) 。
定义一个非负整数序列的代价为从一个全 0
序列操作得到该序列所需要花费的最小代价。
先给定 \(N\) 和 \(K\) 以及一个 \(N
\times K\) 的非负整数矩阵 \(B\)
，依次将每个 \(A_i\) 赋值为 \(B_{i,1}, B_{i,2} ... B_{i,K}\) ，求所有
\(K^N\) 个可能的 \(A\) 序列的代价的和。
时间复杂度：\(O(N^2 K (K + C))\)
。
题解
子问题引入
先来考虑对于给定的长度为 \(N\)
的序列 \(A\) ，如何求出 \(A\) 的代价？
不妨先进行所有 2 操作得到序列 \(D\)
，然后对 \(D\) 执行 1 操作得到 \(A\) ，如果 \(D\)
确定的话两个操作的代价都是容易求的，总代价即（默认 \(D_0 = 0\)）：
\[
\sum_{i=1}^N C \max(D_i - D_{i-1}, 0) + |A_i - D_i|
\]
据此不难想到一个 DP ，设 \(f_{i,j}\)
表示钦定 \(D_i = j\) 的前提下上式前
\(i\) 项的最小值，转移有
\[
f_{i,j} = \min_{k \ge 0} (f_{i-1,k} + C \max(j - k, 0) + |j - A_i|)
\]
设 \(F_i(x) = f_{i,x}\)
，接下来我们证明，\(F_i(x)\)
总是凸函数（离散意义上）。
凸性证明
采用数学归纳法，对于 \(i = 0\)
，我们不妨令 \(F_0(x) = (C + 1) x\)
。
设 \(G(x) = F_i(x) - |x - A_i|\)
，如果 \(G(x)\) 是凸的，由于 \(|x - A_i|\) 也是凸的，就可以证明 \(F_i(x)\) 是凸的。
\(F_{i-1}(x)\) 最小值取在 \(x = k\) 。那么首先显而易见的是：
\[
\forall x \in [0, k], G(x) = F_{i-1}(k)
\]
设 \(x_0\) 是最大的满足 \(G(x_0) - G(x_0 - 1) < C\)
的值，那么可以发现
\[
\forall x \in [k + 1, x_0], G(x) = F_{i-1}(x)
\]
对于 \(x > x_0\) 的部分，由于
\(F_{i-1}(x)\)
增长过快，最优的转移点就不会变了，因此
\[
\forall x \ge x_0 + 1, G(x) = F_{i-1}(x_0) + C (x - x_0)
\]
那么 \(G(x)\)
被分为三个部分，第一部分是斜率为 \(0\)
的折线，第二部分基于归纳假设是凸的斜率在 \([1,
C - 1]\) 内的折线，第三部分是斜率为 \(C\) 的折线，因此 \(G(x)\) 是凸的，\(F_i(x)\) 也是凸的。
问题简化
注意到 \(G(x)\) 是一个折线，由斜率从
\(0\) 到 \(C\)
的线段依次组成，这意味着折线的端点至多有 \(C\) 个，不妨设 \(X_i\) 表示斜率为 \(i\) 的线段的起点横坐标，我们考虑通过维护
\(X_i\) 来间接维护 \(G(x)\) 所代表的折线。
首先我们要支持在 \(G(x)\) 上加上
\(|x - A_i|\)
，可以发现这个操作后，\(A_i\)
左侧的直线都减小了 \(1\) ，\(A_i\) 右侧的直线都增加了 \(1\) ，这其实就是在 \(X\) 序列里添加两个 \(A_i\) 。
紧跟着我们要把 \(G(x)\)
进行一次转移，也就是按照前面所说的分成三段，第一段就是把斜率为 \(-1\) 的直线调整为斜率为 \(0\) ，第二段不变，第三段是把斜率为 \(C+1\) 的直线调整为斜率为 \(C\) 。那么事实上，这就是在 \(X\) 序列里头删掉最小值和最大值。
而每次查询 \(G(x)\)
的最小值的位置，也就是每次被删掉的最小值。
综上所述，求一个序列 \(A\)
的代价的过程可以被描述为：
- 建立一个可重集 \(S\) ，包含 \(C\) 个 \(0\) 。
- 从小到大对于每个 \(i\) ，将两个
\(A_i\) 放入 \(S\) 中，将答案加上 \(A_i - \min S\) ，然后删除 \(S\) 中的最小值和最大值
DP 计数
现在回到原问题，怎么记数。
不妨对于每个值 \(x\) ，求出它在
\(S\) 中作为最小值被删去的次数 \(tot(x)\) 。枚举值 \(x\) ，由于只关注大小，不妨把小于 \(x\) 的数都看做 \(0\) ，不小于 \(x\) 的数都看做 \(1\) ，这样一来 \(S\) 中始终只有 \(0\) 和 \(1\) ，可以用 \(1\) 的数量表示 \(S\) 。设 \(h_{i,j}\) 表示考虑刚加入两个 \(A_i\) 时 \(S\) 中有恰好 \(j\) 个 \(1\) 的方案数，然后不难算出
\[
\sum_{i=0}^{x-1} tot(i) = \sum_{i=1}^N \sum_{j=0}^{C+1} h_{i,j} = K^N -
\sum_{i=1}^N h_{i,C+2}
\]
最后答案即
\[
\sum_{i=1}^N \sum_{j=1}^K (K^{N-1} - tot(B_{i,j})) B_{i,j}
\]
