AT_ABC307_G-Approximate Equalization
没想到还有Approximate Equalization II ！！：AT_ABC313_C
Description:
- 给定一个长度为 \(N\) 的数列：\(A = (A_1,A_2,···,A_N)\)，有两种操作可以以任意顺序进行任意多次（可以为0）：
- \(A[i]-\)=\(1\) 且 \(A[i+1]+\)=\(1\)，\((1\leq i \leq N-1)\)
- \(A[i]+\)=\(1\) 且 \(A[i+1]-\)=\(1\)，\((1\leq i \leq N-1)\)
- 求出使得数列 \(A\) 满足 \(\forall (i,j),|A_i-A_j|\leq 1\) 所需的最少操作次数。
Constraints:
- \(2 \leq N \leq 5000\)
- \(-10^9 \leq A_i \leq 10^9\)
Analysis:
- 无论如何操作，\(sum=\sum A_i\) 恒为定值，则操作方向为让数列趋向于平均值 \(ave\)，进一步细化，则终态数列 \(B\) 仅由 \(ave\) 和 \(ave+1\)，且分别的个数可求 \((x,y)\)。
法一：
\[\left\{ \begin{aligned} &y = sum \% n \\ &x = n-y \end{aligned} \right. \]
法二：
\[\left\{ \begin{aligned} &x+y = n \\ &x\times res+y\times (res+1)=sum=\sum{A_i} \end{aligned} \right. \]
- 发现 \(n\) 的范围并不大，结合终态每转换一位仅有两种状态，故可考虑序列\(dp\)，复杂度 \(O(n^2)\)
- \(dp[i][j]\) 表示前 \(i\) 个数中有 \(j\) 个 \((ave+1)\) 的最小操作数，此时有 \((i-j)\) 个 \(ave\)
- 状态转移：因为问题中每次操作都是将 \(i\) 和 \(i+1\) 捆绑修改，现在我们考虑前 \(i\) 个数操作，最多影响区间 \([1,i+1]\)，显然前 \(i+1\) 个数的总和不变，已知原来前 \(i+1\) 个数的和（当然使用前缀和来维护），同时结合目前的 \(dp\) 状态，我们知道已经有了 \(i-j\) 个 \(ave\) 和 \(j\) 个 \((ave+1)\)，所以便可求得改变后的 \(a_{i+1}\)
即\(new\_a=pre[i+1]-(i-j)\times ave-j\times (ave+1)\)
则新增的操作数即为 \(op_1=|new\_a-ave|\) 或 \(op_2=|new\_a-(ave+1)|\) - 转移方程：
\(dp[i+1][j]=min \{dp[i][j]+op_1,dp[i+1][j]\}\)
\(dp[i+1][j+1]=min \{dp[i][j]+op_2,dp[i+1][j+1]\}\) - 代码细节要注意：！！
- c++对于 负数 整除和取模的处理需要微调一下（不像python...），例如\(-3 \div 5=0\neq -1...\) \(-3\%5=-3\neq2\)
- 不开long long 见祖宗（
绷绷绷）
Solution:
ll dp[maxn][maxn];
ll sum;
void solve() {
int n; cin >> n;
vector<ll> a(n+1),pre(n+1);
for(int i=1;i<=n;i++) {
cin >> a[i];
sum += a[i];
pre[i] = pre[i-1] + a[i];
}
ll ave = sum / n;
if(ave * n > sum) ave--;
int y = sum - ave * n; // ave+1
int x = n - y; // ave
memset(dp,0x3f,sizeof(dp));
dp[0][0] = 0;
for(int i=0;i<=n-1;i++) {
for(int j=0;j<=i;j++) {
ll val = (i-j)*ave+j*(ave+1);
ll new_a = pre[i+1] - val;
dp[i+1][j] = min(dp[i][j]+abs(new_a-ave),dp[i+1][j]);
dp[i+1][j+1] = min(dp[i][j]+abs(new_a-(ave+1)),dp[i+1][j+1]);
}
}
cout << dp[n][y] << endl;
}