题目描述
Pine 开始了从地到地的征途。
从地到地的路可以划分成段,相邻两段路的分界点设有休息站。
Pine 计划用天到达地。除第天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。
设方差是,可以证明,是一个整数。为了避免精度误差,输出结果时输出。
输入格式
第一行两个数、。
第二行个数,表示段路的长度。
题解
CCF不考DP了(悲)
假设有一个序列,平均数是,那么它的方差就是
所以原问题就变成:将个数分为段,假设第段内的所有数之和为,求的最小值
设表示将前个数分成段的最小平方和
容易得到转移方程:,表示前缀和
变换一下得到
这样就可以进行斜率优化,维护的凸壳来转移出
由于数组单调递增,所以直接用单调队列维护下凸壳即可
时间复杂度
代码
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 38 39 40 41 42 43 44 45 46 47
| #include <bits/stdc++.h> #define N 5005 using namespace std; typedef long long ll;
template<typename T> inline void read(T &num) { T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
int n, m, head, tail, q[N]; ll a[N], f[2][N], x[N], y[N];
inline double slope(int p, int q) { if (x[p] == x[q]) return 1e15; else return 1.0 * (y[p] - y[q]) / (x[p] - x[q]); }
int main() { read(n); read(m); for (int i = 1; i <= n; i++) { read(a[i]); a[i] += a[i-1]; } int o = 0; for (int i = 1; i <= m; i++) { o = i & 1; head = 1; tail = 0; for (int j = 0; j <= n; j++) { if (i > 1 || j == 0) { while (head < tail && slope(q[tail-1], q[tail]) > slope(q[tail], j)) tail--; q[++tail] = j; } while (head < tail && slope(q[head], q[head+1]) < (double)a[j]) head++; int k = q[head]; f[o][j] = f[!o][k] + (a[j]-a[k]) * (a[j]-a[k]); } for (int j = 0; j <= n; j++) { f[!o][j] = 0; x[j] = 2 * a[j]; y[j] = f[o][j] + a[j] * a[j]; } } printf("%lld\n", f[m&1][n] * m - a[n] * a[n]); return 0; }
|