题目分析
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
分析
比较简单的斜率优化。
\[f[i][j]=min(f[k][j-1]+m(sum[i]-sum[j])^3-s\times s_n(s_i-s_j))\]
答案就是\(f[n][m]+sn^2\)
化简玩后滚动数组优化一下。
代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define db double
#define N 3005
using namespace std;
int a[N];
ll sum[N], f[N], g[N], q[N];
int n, m;
ll sqr(ll x) {
return x * x;
}
ll X(int i) {
return sum[i];
}
ll Y(int i) {
return g[i] + sqr(sum[i]);
}
db slope(int i, int j) {
return (1.0 * Y(j) - 1.0 * Y(i)) / (1.0 * X(j) - 1.0 * X(i));
}
ll calc(int l, int r) {
return sqr(sum[r] - sum[l - 1]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i], g[i] = sqr(sum[i]);
for (int k = 1; k < m; k ++) {
memset(f, inf, sizeof(f));
int h = 0, t = 0; q[0] = k;
for (int i = k + 1; i <= n; i ++) {
while (h < t && slope(q[h], q[h + 1]) < 2 * sum[i]) h ++;
int j = q[h];
f[i] = min(f[i], g[j] + calc(j + 1, i));
while (h < t && slope(q[t - 1], q[t]) > slope(q[t], i)) t --;
q[++ t] = i;
}
memcpy(g, f, sizeof(g));
}
printf("%lld\n", f[n] * m - sum[n] * sum[n]);
return 0;
}