传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4518
首先推式子，我们用$x_i$表示第$i$段的路程，$sum$表示总路程，根据方差和平均数的定义，有：
$ \Large sum = \sum\limits_{i=1}^{m}{x_i} \\ $
$ \Large \bar{x} = \frac{sum}{m} \\ $
$ \Large ans = \frac{ \sum\limits_{i=1}^{m}{ (x_i - \bar{x})^2 } }{m} \cdot m^2 \\ $
然后我们把式子展开化简一番，就有了：
$ \Large ans = ( \sum\limits_{i=1}^{m}{ (x_i - \frac{sum}{m})^2 } ) \cdot m \\ $
$ \Large ans = ( \sum\limits_{i=1}^{m}{ \frac{ (m \cdot x_i - sum)^2 }{m^2} } ) \cdot m \\ $
$ \Large ans = \sum\limits_{i=1}^{m}{ \frac{ m^2 \cdot x_i^2 - 2 \cdot m \cdot x_i \cdot sum + sum^2 }{m} } \\ $
$ \Large ans = sum^2 + \sum\limits_{i=1}^{m}{ (m \cdot x_i^2 - 2 \cdot x_i \cdot sum) } \\ $
于是我们的目标就是最小化这个式子，看上去很像个dp？没错。
先抛开前面的常数$sum^2$，我们下面的dp过程中计算的是后面那个求和式子的最小值。
设$f(i,j)$表示我们把前$j$个数划分成了$i$段的最小值，$dist(i,j)$表示从第$i$个数到第$j$个数的和，用$d$数组存放前缀和，于是有：
$ \Large dist(i,j) = d_j - d_{i-1} \\ $
$ \Large f(i,j) = f(i-1,k) + m \cdot dist(k+1,j)^2 - 2 \cdot dist(k+1,j) \cdot sum \\ $
对这个式子展开并化简，得到：
$ \Large f(i,j) = f(i-1,k) + m \cdot (d_j - d_k)^2 - 2 \cdot (d_j - d_k) \cdot sum \\ $
$ \Large f(i,j) = f(i-1,k) + m \cdot (d_j^2 - 2 \cdot d_j \cdot d_k + d_k^2 ) - 2 \cdot d_j \cdot sum + 2 \cdot d_k \cdot sum \\ $
再整理一下式子，我们就可以进行斜率优化dp了，下面的$x$和$y$表示状态对应的点的横纵坐标，$k$表示状态对应的斜率，$b$表示状态对应的常数项。
$ \Large b = m \cdot d_j^2 - 2 \cdot d_j \cdot sum \\ $
$ \Large y = f(i-1,k) + m \cdot d_k^2 + 2 \cdot d_k \cdot sum \\ $
$ \Large x = d_k \\ $
$ \Large k = 2 \cdot m \cdot d_j \\ $
$ \Large f(i,j) = y - x \cdot k + b \\ $
我们的任务是最小化$f(i,j)$，且$x,y,k$是递增的，于是就用单调队列维护一个下凸壳就好啦。
代码：
1 #include <cstring> 2 #include <cstdio> 3 #include <algorithm> 4 5 using namespace std; 6 typedef long long ll; 7 const double EPS = 1e-6; 8 const int MAXN = 3010; 9 10 struct Point { 11 ll x, y; 12 Point( ll x = 0, ll y = 0 ):x(x),y(y){} 13 Point operator-( const Point &rhs ) const { 14 return Point(x-rhs.x, y-rhs.y); 15 } 16 }; 17 typedef Point Vector; 18 double Cross( Vector v, Vector w ) { 19 return (double)v.x*w.y - (double)v.y*w.x; 20 } 21 22 namespace MonoQ { // 维护下凸壳的单调队列 23 Point P[MAXN]; 24 int head, tail; 25 void clear() { 26 head = tail = 0; 27 } 28 void insert( Point Q ) { // 插入一个点 29 while( tail-head >= 2 && Cross(P[tail-1]-P[tail-2], Q-P[tail-1]) < EPS ) --tail; 30 P[tail++] = Q; 31 } 32 Point query( ll k ) { // 根据斜率查询最小值 33 while( tail-head >= 2 && P[head].y - P[head].x*k > P[head+1].y - P[head+1].x*k ) ++head; 34 return P[head]; 35 } 36 } 37 38 ll n, m, d[MAXN] = {0}; 39 40 ll f[2][MAXN]; 41 ll getx( int i ) { // 这四个函数用于获取一个状态对应的几何信息 42 return d[i]; 43 } 44 ll gety( int cur, int i ) { 45 return f[cur][i] + m*d[i]*d[i] + 2*d[i]*d[n]; 46 } 47 ll getb( int i ) { 48 return m*d[i]*d[i] - 2*d[i]*d[n]; 49 } 50 ll getk( int i ) { 51 return 2*m*d[i]; 52 } 53 void solve() { 54 int cur = 0; 55 memset( f, 0x3f, sizeof(f) ); 56 f[cur][0] = 0; 57 for( int i = 1; i <= m; ++i ) { 58 cur ^= 1; 59 MonoQ::clear(); 60 MonoQ::insert( Point(getx(i-1), gety(cur^1, i-1)) ); 61 for( int j = i; j <= n; ++j ) { 62 Point P = MonoQ::query(getk(j)); 63 f[cur][j] = P.y - P.x*getk(j) + getb(j); 64 MonoQ::insert( Point(getx(j), gety(cur^1, j)) ); 65 } 66 } 67 printf( "%lld\n", f[cur][n] + d[n]*d[n] ); // 别忘了最后加上sum^2 68 } 69 70 int main() { 71 scanf( "%lld%lld", &n, &m ); 72 for( int i = 1; i <= n; ++i ) { 73 scanf( "%lld", d+i ); 74 d[i] += d[i-1]; // 前缀和 75 } 76 solve(); 77 return 0; 78 }