[ABC307G] Approximate Equalizatio
题意
给定一个数组 \(a_i\) ，有两种操作。
- \(a_i+1,a_{i+1}-1\)
- \(a_i-1,a_{i+1}+1\)
问最少花费多少次操作能使数组的极差不超过 \(1\)。
题解
题目其实并不难，容易发现总和不变，由于极差不超过 \(1\) ，设平均数为 \(s\) ，则数组中只有 \(s\) 和 \(s+1\) 两种取值，其中 \(s+1\) 显然只有 \(sum\) % \(n\) 个。
若直接给定结束后的状态，直接从左往右操作，每次直接变成目标，直接将影响交给下一个数，这样其实已经是最小操作次数了。
也就是说设最初 \(i\) 的前缀和为 \(s_i\) ，在结束状态中为 \(s'_i\) ，在 \(i\) 这个位置的操作数为 \(\vert s_i - s'_i \vert\)。
但是现在不知道最终状态，考虑到数据中 \(n\) 只有 \(5000\) ， 所以我们可以使用 \(dp\) 来解决。
容易想到 \(f_{i,j}\) 表示前 \(i\) 个，有 \(j\) 个是 \(s+1\) ，有了这两个我们可以轻易的求出 \(s'_i\) ，之后转移也就很简单了。 code
ps:若总和为负数，所有数字都乘上 \(-1\) 即可，因为操作可以反转。
...
感觉这道题的难点在于想到 \(dp\) 和 \(dp\) 的状态设计，转移倒是很简单。
为什么会想到 \(dp\) 呢，我们需要的是最终状态的前缀和，同时题目支持我们将当前 \(s+1\) 的个数压入状态。
而 \(s+1\) 的个数又能够让我们推出前缀和，\(dp\) 显然可以解决。