给定n段路的长度，每天可以走连续的几段路，要求你走m天，并最小化每天走的路程长度的方差$\times m^2$的大小$n \leq 3000,m \leq 3000$
做法
方差：$\frac{1}{m}\sum (x_i - \bar{x})^2m$ = $\frac{1}{m}(\sum x_i^2 + \sum \bar{x}^2 - 2\sum x_i\bar{x}) = \sum x_i$$\frac{1}{m}(\sum (x_i - \bar{x})^2) = m(\sum x_i^2 - \bar{x}\sum x_i)$ = $m\sum x_i^2 - (\sum x_i)^2$容易发现后一项是定值，所以只需要最小化$\sum x_i^2$即可$dp_{i,j}$表示前i段路走了j天的最小方差$dp_{i,j} = \min \limits_{k<i} \{dp_{k,j-1} + (sum_i-sum_k)^2\}$每次询问$sum_i$处y的最小值，然后插入一条斜率为$-2sum_i$，截距为$sum_i^2 + dp_{i,j-1}$的直线。斜率单调递减，询问单调递增，双端队列维护下凸壳即可通过斜率优化就可以$n^2$通过本题
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
const int N = 3e3 + 5;
int n, m, d[N];
ll sum[N], dp[N][2];
struct Line
{
ll k, b;
ll eval(ll x) { return k*x + b; }
db insect(Line oth) { return db(b-oth.b)/(oth.k-k); }
}q[N];
int ql, qr;
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d", d+i), sum[i] = sum[i-1] + d[i], dp[i][0] = sum[i]*sum[i];
int p = 1;
ll ans = dp[n][0];
for(int c=2; c<=m; c++, p^=1)
{
q[ql=qr=1] = {0, 0};
for(int i=1; i<=n; i++)
{
while(ql<qr && q[ql].insect(q[ql+1])<=sum[i]) ++ql;
dp[i][p] = q[ql].eval(sum[i]) + sum[i]*sum[i];
Line cur = {-2*sum[i], sum[i]*sum[i]+dp[i][p^1]};
while(ql<qr && cur.insect(q[qr])<=cur.insect(q[qr-1])) --qr;
q[++qr] = cur;
}
ans = min(ans, dp[n][p]);
}
printf("%lld\n", m*ans-sum[n]*sum[n]);
return 0;
}
|