【题解】征途 SDOI 2016 BZOJ 4518

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4518

首先推式子，我们用$x_i$表示第$i$段的路程，$sum$表示总路程，根据方差和平均数的定义，有：

$ Large sum = sumlimits_{i=1}^{m}{x_i} \ $
$ Large ar{x} = frac{sum}{m} \ $
$ Large ans = frac{ sumlimits_{i=1}^{m}{ (x_i - ar{x})^2 } }{m} cdot m^2 \ $

然后我们把式子展开化简一番，就有了：

$ Large ans = ( sumlimits_{i=1}^{m}{ (x_i - frac{sum}{m})^2 } ) cdot m \ $
$ Large ans = ( sumlimits_{i=1}^{m}{ frac{ (m cdot x_i - sum)^2 }{m^2} } ) cdot m \ $
$ Large ans = sumlimits_{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 + sumlimits_{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$是递增的，于是就用单调队列维护一个下凸壳就好啦。

代码：

#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const double EPS = 1e-6;
const int MAXN = 3010;

struct Point {
    ll x, y;
    Point( ll x = 0, ll y = 0 ):x(x),y(y){}
    Point operator-( const Point &rhs ) const {
        return Point(x-rhs.x, y-rhs.y);
    }
};
typedef Point Vector;
double Cross( Vector v, Vector w ) {
    return (double)v.x*w.y - (double)v.y*w.x;
}

namespace MonoQ { // 维护下凸壳的单调队列
    Point P[MAXN];
    int head, tail;
    void clear() {
        head = tail = 0;
    }
    void insert( Point Q ) { // 插入一个点
        while( tail-head >= 2 && Cross(P[tail-1]-P[tail-2], Q-P[tail-1]) < EPS ) --tail;
        P[tail++] = Q;
    }
    Point query( ll k ) { // 根据斜率查询最小值
        while( tail-head >= 2 && P[head].y - P[head].x*k > P[head+1].y - P[head+1].x*k ) ++head;
        return P[head];
    }
}

ll n, m, d[MAXN] = {0};

ll f[2][MAXN];
ll getx( int i ) { // 这四个函数用于获取一个状态对应的几何信息
    return d[i];
}
ll gety( int cur, int i ) {
    return f[cur][i] + m*d[i]*d[i] + 2*d[i]*d[n];
}
ll getb( int i ) {
    return m*d[i]*d[i] - 2*d[i]*d[n];
}
ll getk( int i ) {
    return 2*m*d[i];
}
void solve() {
    int cur = 0;
    memset( f, 0x3f, sizeof(f) );
    f[cur][0] = 0;
    for( int i = 1; i <= m; ++i ) {
        cur ^= 1;
        MonoQ::clear();
        MonoQ::insert( Point(getx(i-1), gety(cur^1, i-1)) );
        for( int j = i; j <= n; ++j ) {
            Point P = MonoQ::query(getk(j));
            f[cur][j] = P.y - P.x*getk(j) + getb(j);
            MonoQ::insert( Point(getx(j), gety(cur^1, j)) );
        }
    }
    printf( "%lld
", f[cur][n] + d[n]*d[n] ); // 别忘了最后加上sum^2
}

int main() {
    scanf( "%lld%lld", &n, &m );
    for( int i = 1; i <= n; ++i ) {
        scanf( "%lld", d+i );
        d[i] += d[i-1]; // 前缀和
    }
    solve();
    return 0;
}