「SDOI 2016」征途【DP + 斜率优化】

Time Limit: 10 Sec Memory Limit: 256 MB

Description

Pine 开始了从 SS 地到 TT 地的征途。从 SS 地到 TT 地的路可以划分成 nn 段,相邻两段路的分界点设有休息站。Pine 计划用 mm 天到达 TT 地。除第 mm 天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。

请帮助 Pine 求出最小方差是多少。设方差是 vv,可以证明,v×m2v \times m^2 是一个整数。为了避免精度误差,输出结果时输出 v×m2v \times m^2

Input

11 行包含两个整数 n,mn, m
22 行包含 nn 个数,表示 nn 段路的长度。

Output

输出一个数,即最小方差乘以 m2m^2 后的值

Sample Input

1
2
5 2
1 2 5 8 6

Sample Output

1
36

Constraints

1n30001 \leqslant n \leqslant 3000。保证从 SSTT 的总路程不超过 3000030000

Solution

aia_i 为每一天的路程,S(i)=j=1iaj\displaystyle S(i)=\sum_{j=1}^i a_j,则要最小化 m2i=1m(aiS(n)m)2m\displaystyle m^2 \cdot \sum_{i=1}^m \frac{(a_i - \frac{S(n)}{m})^2}{m}

将上式整理得

 m2i=1m(aiS(n)m)2m=m2(i=1mai2m+i=1m(S(n))2m32i=1maiS(n)m2)=mi=1mai2S(n)2\begin{aligned} &\quad \ m^2 \cdot \sum_{i=1}^m \frac{(a_i - \frac{S(n)}{m})^2}{m} \\ &= m^2 \cdot \Big(\sum_{i=1}^m \frac{a_i^2}{m} + \sum_{i=1}^m \frac{\big(S(n)\big)^2}{m^3} - 2 \sum_{i=1}^m a_i \frac{S(n)}{m^2}\Big) \\ &= m \cdot \sum_{i=1}^m a_i^2 - S(n)^2 \end{aligned}

m,S(n)2m, S(n)^2 是常数,所以只要最小化 i=1mai2\displaystyle \sum_{i=1}^m a_i^2 即可。

方法一

f(j,i)f(j, i) 为前 ii 段路分成 jj 天最优方案的值,则

f(j,i)=mink=1j1{f(j1,k)+[S(i)S(k)]2}f(j, i) = \min_{k=1}^{j-1} \Big\{f(j-1, k) + \big[S(i) - S(k)\big]^2\Big\}

时间复杂度为 O(nm2)O(n \cdot m^2),超时。

方法二

观察知状态的第一位是可以滚动的,设 g(i)=f(j1,i)g(i) = f(j-1, i)

考虑两个决策 k=ak=ak=bk=b,若 aabb 更优,当且仅当

[g(a)+sa2][g(b)+sb2]sasb<2Si\frac{\big[g(a) + s_a^2\big] - \big[g(b) + s_b^2\big]}{s_a - s_b} < 2 \cdot S_i

直接斜率优化动态规划,时间复杂度为 O(nm)O(n \cdot m),可以通过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 3010;
int n, m, a[maxn], S[maxn], q[maxn];
ll f[maxn], g[maxn];

double slope(int i, int j) {
return (double)(g[i] - g[j] + S[i] * S[i] - S[j] * S[j]) / (double)(S[i] - S[j]);
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
S[i] = S[i - 1] + a[i];
}
fill(f + 1, f + n + 1, INT_MAX);
for (int j = 1; j <= m; j++) {
memcpy(g, f, sizeof(f)), memset(f, 0, sizeof(f));
int l = 0, r = -1;
q[++r] = 0;
for (int i = 1; i <= n; i++) {
while (l < r && slope(q[l + 1], q[l]) < 2 * S[i]) {
l++;
}
f[i] = g[q[l]] + (S[i] - S[q[l]]) * (S[i] - S[q[l]]);
while (l < r && slope(q[r], q[r - 1]) > slope(q[r], i)) {
r--;
}
q[++r] = i;
}
}
printf("%d\n", f[n] * m - S[n] * S[n]);
return 0;
}