估计是全网最复杂题解。。。
反向考虑：将 \(a_i\) 进行减操作，使得每个数都小于等于 0。考虑差分，差分后将区间减转变为单点的加减，但是这样一来每个数都小于等于 0 的判定就变成了要判定前缀和是否都小于等于 0，这不太好处理。
考虑增加一个区间加操作，对 \([l,r]\) 的区间内的 \(a_i\) 加 1，花费为 0。可以想象为通过原本的操作把 \(a_i\) 操作至非正后，又把负数全部再加回 0。这样一来相当于通过增加一个“不优”的操作将终止条件从全部非正转化为了全部都要是 0，方便后续讨论。
看看现在问题是什么。给定一个数组 \(a_i\)，其中有正有负。操作1（前缀）：\(a_1-=1\)，\(a_{r+1}+=1\)，花费代价 \(r\)。操作2（后缀）：\(a_l-=1\)，花费代价 \(n-l+1\)。操作3（调整）：\(a_x+=1\)，\(a_y-=1\)，满足 \(x<y\)，花费为 0。通过这三个操作，将 \(a_i\) 全部变为 0，求最小代价。
几个观察：
首先，操作是满足交换律的，也就是说最优解中的操作序列打乱顺序后依然是最优解。
由于 \(a_i\) 中的数全部要变为 0，那么我们不会把正数变大，不会把负数变小，也不会对 0 做任何操作。
假设没有负数，最优方案很显然：对每个正数做操作2直到变小至0。但有了负数之后，这样做就不优了，这是因为负数能够在一定程度上优化正数变小的开销。举例说，如果有一个 “ ... -1 ... +1 ...”，我们可以通过操作3，不消耗任何代价使得后面的 +1 变为 0；如果有一个 " ... +1 ... -1 ..."，我们先通过对 -1 进行操作1，花费代价 r 将 -1 转移到 \(a_1\) 去，然后就转化成了上面的情况，再使用操作3即可。这相当于花费 r，使得前面的 +1 变为 0。具体的，假设说 +1 在位置 \(i\)，-1 在位置 \(j\)，如果 \(j<i\)，即 -1 在 +1 前面，我们可以让 +1 的原本的 \(n-i+1\) 的花费降低至 0；如果 \(j>i\)，可以把花费降低至 \(j-1\)。
有了上面的观察，我们可以进一步转化题目：先不考虑负数，只用操作2把所有正数变成 0 并计算花费，然后剩下一堆负数没有用，再考虑负数能够通过操作1、3最多挽回多少损失。一个 -1 通过操作3，可以退回右侧 +1 之前的操作2的开销；通过操作1+操作3，可以退回左侧 +1 之前的操作2的开销。
具体来说，假设说有一个 -1 在 \(j\) 的位置，它可以通过操作1和3去处理一个在 \(j\) 之前的 \(i\) 处的 +1，挽回 \(w(j)=n-i+1-(j-1)\) 的花费，也可以选择通过操作3去处理一个在 \(j\) 之后的 \(k\) 处的一个 +1，挽回 \(w(k)=n-k+1\) 的花费。这两个花费分别就是在左侧的 +1 和在右侧的 +1 的价值。
问题变成了每一个负数的抉择：分多少 -1 给左边，分多少 -1 给右边？
这里我们使用贪心策略，每一次选择当前能够挽回最多代价的一对 -1 和 +1。这样的最优配对有什么特征？
我们发现，不论最优配对的 +1 在哪里，其配对的 -1 一定是当前在最左边的那个 -1（操作1花费最小，且能对最多正数做操作3）。也就是说，越靠左的 -1 越厉害，而且最优配对的 -1 一定是最左边的 -1。
所以每一次最佳配对的 -1 都是确定的，只需要每次找到最优的 +1 ，也就是要找到使得 \(w(j)\) 最大的 j。
注意到：
- 越靠左的 +1 消耗的操作2的代价越大，选择它能挽回的代价就越多。
- 同在左侧的 +1 都需要 -1 做一次操作1，同在右侧的 +1 都不需要这个操作1。
综上，最优的 +1 一定是 -1 两侧的最左边的两个 +1 中的一个。比较一下选择最优的即可。
但上述讨论姑且只是在只考虑一步的情况下的最优解，如果允许先前已经配对好的 -1 重新决定配对，当前最优的 +1 可能会变化。也就是说，之前已经做出的局部最优抉择可能会在后面发现不是最优的，需要进行反悔。
情况1： "... +1 ... -1 ... +1 ... -1 ..."：先前考虑到 2 时，组成了配对 (2,1)，然后在考虑到 4 时，组成了配对 (4,3)，目前为止每一步配对都在当时是最优的。但现在我们知道，如果我们对于”在考虑 2 时做出的抉择“进行反悔：让 2 不再和 1 配对而是和 3 配对，然后失去配对的 1 由 4 接管，那么就可以省去一个操作1（省去一个 \(i_2-1\) 的代价）。即 (2,1)(4,3) 可以反悔成 (2,3)(4,1)。如何进行反悔？
考虑进行反悔后会发生什么。如果应用了这个反悔，我们发现：当前情况下选择将位于 3 的 +1 下降所能挽回的最多的价值其实不是 \(n-i_3+1-(i_4-1)\) 而是 \(n-i_3+1-(i_4-1)+(i_2-1)\)。所以，原先对处于当前 -1 的左边的 +1 做出的估价函数，可以再增加一项。
在当前考虑的 -1(i) 的左边的 +1(j)，如果它的左边还有一个最近的一个先前抉择好的配对 \((p,q)\)，满足 \(q<p<j<i\) 且 p 最大，那么通过配对 \((p,j)(i,q)\)，计算得新的价值函数 \(w'(j)=n-j+1-(i-1)+(p-1)\)。这个价值函数相比于先前的，能够多挽回 \(p-1\) 的价值。
通过允许反悔，优化了左侧 +1 的估价函数，反过来说，通过获取更新后的价值，也相当于自动完成了对先前抉择的反悔。
情况2：" +1 ... -1 -1 +1 ..."：位于 2 的 -1 在当时选择了右边最近的 +1，即与位于 4 的 +1 配对成 (2,4)，但显然全局最优解会选择将 3 与 4 配对。这是因为，如果配对 (3,4)，那么为了消去 1 所需要的操作1，可以由 2 而不是 3 来做，优化了操作 1 的花费。即 (2,4)(3,1) 可以反悔成 (2,1)(3,4)。如何进行反悔？
可以仿照情况一，对能够优化的 +1 的价值函数进行修改。
比如当前考虑到的 -1 位于 \(i\)，且存在一个配对 \((p,q)\) 满足 \(p<i<q\)，那么对于 \(j<p<i<q\) 的 \(j\)，通过配对 \((p,j)(i,q)\) 其价值优化为 \(w'(j)=n-j+1-(p-1)\)，相比于之前多挽回 \(i-p\) 的价值。但这个相比于情况一难处理得多。
实际上，我们可以通过直接避免这种情况的发生来避免反悔。注意到一段连续的 -1 中的每一个与右边最近的 +1 配对时价值相同，但是如果我们总是选择连续段中最右边的 -1 去跟右边的 +1 配对，就不会发生情况2。
故我们不再每次只考虑最左边的一个 -1，而是考虑最左边的连续的一段 -1（内部没有正数），那么左边的 +1 还是会与最左边的 -1 配对，而右边 +1 会与连续段的最右边的 -1 配对。
解决了上述的两种情况，我们可以做到：在综合考虑当前的抉择和过去所有抉择的反悔的情况下，每次都能找到最优的一步选择。这归功于我们找到了允许反悔的情况下的每一个 +1 的价值函数。这样每次选择价值函数最高的 +1 的贪心，最终就可以获得最优解。
这个问题实际上可以转化为费用流问题，上述贪心和反悔实际上是在模拟费用流的进退流过程，因此可以获得严谨的正确性证明。
标签：...,花费,反悔,Add,操作,最优,配对,贪心 From： https://www.cnblogs.com/nkxjlym/p/18504519