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]\}\)
代码细节要注意：！！
1. c++对于负数 整除和取模的处理需要微调一下（不像python...），例如\(-3 \div 5=0\neq -1...\) \(-3\%5=-3\neq2\)
2. 不开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;
}