题解 P4072 【[SDOI2016]征途】

· · 题解

首先，我们先把结果的表达式化简一下

假设第i天走了x_i，总路程为S

那么ans=m^2\times \frac{\sum \limits_{i=1}^m(x_i-\frac{S}{m})^2}{m}=\frac{\sum\limits_{i=1}^m(mx_i-S)^2}{m}=\frac{m^2\sum \limits_{i=1}^mx_i^2+S^2m-2Sm\sum \limits_{i=1}^mx_i}{m}=m\sum \limits_{i=1}^{m}x_i^2+S^2-2S^2=m\sum \limits_{i=1}^{m}x_i^2-S^2

所以，我们只需要计算最小的\sum \limits_{i=1}^mx_i^2

假设f_{i,j}表示用j天走完前i段时，最小的\sum \limits_{k=1}^jx_k^2的值

为了方便，我们先预处理出sum_i表示前i段的长度之和

所以，我们就可以写出状态转移方程：f_{i,j}=\min \limits_{1\leqslant k<i}\{f_{k,j-1}+(sum_i-sum_k)^2\}

显然，这么做的时间复杂度太高了，我们需要进行优化

怎么优化呢？我们考虑k比l优，那么，我们可以得出：

f_{k,j-1}+sum_k^2+sum_i^2-2sum_ksum_i<f_{l,j-1}+sum_l^2+sum_i^2-2sum_isum_l f_{k,j-1}-f_{l,j-1}+sum_k^2-sum_k^2<2sum_i(sum_k-sum_l) \frac{f_{k,j-1}-f_{l,j-1}+sum_k^2-sum_k^2}{sum_k-sum_l}<2sum_i

所以，我们就可以进行斜率优化了！

附上代码：

#include<cstdio>
int n,m,l,r;
long long a[3010],sum[3010],f[3010],fl[3010],q[3010];
long long K(int x,int y)
{
    return (fl[y]-fl[x]+sum[y]*sum[y]-sum[x]*sum[x])/(sum[y]-sum[x]);
}
int main()
{
    scanf("%d%d",&n,&m),sum[0]=0;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++) fl[i]=sum[i]*sum[i];
    for(int i=2;i<=m;i++){
        l=r=1,q[l]=i-1;
        for(int j=i;j<=n;j++){
            while(l<r&&K(q[l],q[l+1])<2*sum[j]) l++;
            f[j]=fl[q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
            while(l<r&&K(q[r-1],q[r])>K(q[r],j)) r--;
            q[++r]=j;
        }
        for(int j=1;j<=n;j++) fl[j]=f[j];
    }
    printf("%lld",m*f[n]-sum[n]*sum[n]);
}