题意
给定一个长度为 n n n的数组 a a a，以及数组 a a a的所有元素之和 m = ∑ i = 1 n a i m=\sum_{i=1}^na_i m=∑i=1n?ai?。
现在要用最小的操作数将数组
a
a
a变为一个非递增数组
b
b
b，即满足：
b
1
≥
b
2
≥
.
.
.
≥
b
n
b_1\ge b_2\ge...\ge b_n
b1?≥b2?≥...≥bn?。
每次可以选择下面两个操作之一：
- 如果 i > 1 i>1 i>1，可以将 a [ i ] a[i] a[i]的值减1，同时将 a [ i ? 1 ] a[i-1] a[i?1]的值加1.
- 如果 i < n i<n i<n，可以将 a [ i ] a[i] a[i]的值减1，同时将 a [ i + 1 ] a[i+1] a[i+1]的值加1.
思路
如果我们已经得到了移动后的数组 b b b，那么最小操作数可以通过数组 a a a的前缀和 O ( n ) O(n) O(n)算出来。
定义前缀和 p r e a [ i ] = ∑ j = 1 i a [ j ] pre_a[i]=\sum_{j=1}^ia[j] prea?[i]=∑j=1i?a[j]， p r e b [ i ] = ∑ j = 1 i b [ j ] pre_b[i]=\sum_{j=1}^ib[j] preb?[i]=∑j=1i?b[j]：则最小操作数为： ∑ i = 1 n ∣ p r e a [ i ] ? p r e b [ i ] ∣ \sum_{i=1}^n|pre_a[i]-pre_b[i]| ∑i=1n?∣prea?[i]?preb?[i]∣。
解释：
for(int i = 1; i <= n; i++) {
res += abs(a[i] - b[i]);
a[i + 1] += a[i] - b[i];
}
下 标 1 的 贡 献 : ∣ a [ 1 ] ? b [ 1 ] ∣ ∣ p r e a [ 1 ] ? p r e b [ 1 ] ∣ 下 标 2 的 贡 献 : ∣ ( a [ 2 ] + a [ 1 ] ? b [ 1 ] ) ? b [ 2 ] ∣ ∣ p r e a [ 2 ] ? p r e b [ 2 ] ∣ 下 标 3 的 贡 献 : ∣ a [ 3 ] + ( a [ 2 ] + a [ 1 ] ? b [ 1 ] ? b [ 2 ] ) ? b [ 3 ] ∣ ∣ p r e a [ 3 ] ? p r e b [ 3 ] ∣ ? 下 标 n 的 贡 献 : ? ∣ p r e a [ n ] ? p r e b [ n ] ∣ \begin{matrix} 下标1的贡献:&|a[1] - b[1]| & |pre_a[1]-pre_b[1]| \\ 下标2的贡献:&|(a[2] + a[1] - b[1]) - b[2]| & |pre_a[2]-pre_b[2]| \\ 下标3的贡献:&|a[3]+(a[2] + a[1] - b[1]-b[2]) - b[3]| & |pre_a[3]-pre_b[3]| \\ \cdots \\ \\ 下标n的贡献:&\cdots & |pre_a[n]-pre_b[n]| \\ \end{matrix} 下标1的贡献:下标2的贡献:下标3的贡献:?下标n的贡献:?∣a[1]?b[1]∣∣(a[2]+a[1]?b[1])?b[2]∣∣a[3]+(a[2]+a[1]?b[1]?b[2])?b[3]∣??∣prea?[1]?preb?[1]∣∣prea?[2]?preb?[2]∣∣prea?[3]?preb?[3]∣∣prea?[n]?preb?[n]∣?
定义
d
p
[
i
]
[
j
]
[
x
]
dp[i][j][x]
dp[i][j][x] 为
p
r
e
b
[
i
]
=
j
pre_b[i]=j
preb?[i]=j并且
b
[
i
]
=
x
b[i]=x
b[i]=x时需要的最少操作数，那么转移方程为：
{
d
p
[
i
]
[
x
]
[
x
]
=
∣
p
r
e
a
[
1
]
?
x
∣
,
i
=
1
d
p
[
i
]
[
j
]
[
x
]
=
min
?
k
≥
x
{
d
p
[
i
?
1
]
[
j
?
x
]
[
k
]
}
+
∣
p
r
e
a
[
i
]
?
j
∣
,
i
>
1
\left\{ \begin{matrix} dp[i][x][x] &=& |pre_a[1] - x| &, i=1 \\ \\ dp[i][j][x] &=& \min_{k\ge x} \{dp[i - 1][j - x][k]\} + |pre_a[i] - j| &, i>1 \end{matrix} \right.
????dp[i][x][x]dp[i][j][x]?==?∣prea?[1]?x∣mink≥x?{dp[i?1][j?x][k]}+∣prea?[i]?j∣?,i=1,i>1?
看上去好像是 O ( n 4 ) O(n^4) O(n4)，但是算上减枝的话，跑的还挺快的。
#include <bits/stdc++.h>
using namespace std;
const int N = 250 + 10;
int n, m, dp[N][N][N];
int a[N], pre[N];
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.exceptions(ios::badbit | ios::failbit);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= m; i++) dp[1][i][i] = abs(pre[1] - i);
for (int i = 2; i <= n; i++)
for (int x = 0; x <= m; x++)
for (int k = x; k <= m; k++)
for (int j = x + k; j <= m; j++)
dp[i][j][x] =
min(dp[i][j][x], dp[i - 1][j - x][k] + abs(pre[i] - j));
int res = 1e9;
for (int x = 0; x <= m; x++) res = min(res, dp[n][m][x]);
cout << res;
return 0;
}
