「SDOI2016」征途
先浅浅复制一个方差
显然dp，可以搞一个🦁
/(dp[i][j]/)为前i段路程j天到达的最小方差
开始暴力转移
/(dp[i][j]=min(dp[k][j-1]+?)(j-1/leq k/leq i-1)/)这咋写？还是需要转换一下🦁
开始了，but题目的方差还需要✖m^2,很好
以下x为m天行走的平均值，s[i]为1~i段路的总路程
那么x可以算对吧:/(x=/frac{s[n]}{m}/)
/[m/times /sum^m_{i=1}(x_i-x)^2// =m/times /sum^m_{i=1}(x_i^2+x^2-2xx_i)// =m/times (/sum^m_{i=1}x_i^2+/sum^m_{i=1}x^2-/sum^m_{i=1}2xx_i)// =m/times (/sum^m_{i=1}x_i^2+/frac{s[n]^2}{m}-/frac{2s[n]}{m}/sum^m_{i=1}x_i)// =m/times (/sum^m_{i=1}x_i^2+/frac{s[n]^2}{m}-/frac{2s[n]^2}{m})// =m/times (/sum^m_{i=1}x_i^2-/frac{s[n]^2}{m})// =m/times /sum^m_{i=1}x_i^2-s[n]^2 /]
是不是感觉快完了推🦁真爽
所以我们似乎只需要维护/(/sum^m_{i=1}x_i^2/)最小就好了！
重新定义/(dp[i][j]/)为前i段路程分j天到达的每天路程平方的和的最小值
最后答案就应该是/(dp[n][m]/times m-s[n^2]/)
好，开始看状态转移
/(dp[i][j]=min(dp[k][j-1]+(s[i]-s[k])^2)(j-1/leq k/leq i-1)/)很简单的状态转移，但是复杂度/(n^3/)不接受，好像只有/(n^2/)可以的样子（带/(log/)的方法就别杠）
那怎么优化？
我们发现好像是跟/(s[i]*s[k]/)有关，不能直接单调队列，那斜率优化吧！
/[dp[i][j]=dp[k][j-1]+(s[i]-s[k])^2// dp[i][j]=dp[k][j-1]+s[i]^2+s[k]^2-2s[i]s[k]// dp[k][j-1]+s[k]^2=2s[i]s[k]-s[i]^2-dp[i][j]// /]
点为/((s[k],dp[k][j-1]+s[k]^2)/),斜率就是/(2s[i]/)
然后就是愉快的判断是撒子凸壳的时候了，刚学的
假设k1>k2，并且k1优于k2
/[dp[k1][j-1]+s[i]^2+s[k1]^2-2s[i]s[k1]<dp[k2][j-1]+s[i]^2+s[k2]^2-2s[i]s[k2]// dp[k1][j-1]+s[k1]^2-dp[k2][j-1]-s[k2]^2<2s[i](s[k1]-s[k2])// /frac {(dp[k1][j-1]+s[k1]^2)-(dp[k2][j-1]+s[k2]^2)}{(s[k1]-s[k2])}<2s[i] /]
因为是小于，所以是下凸壳，然后就完了噢！
呼，公式真难打
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=3010; int a[maxn]; ll f[maxn][maxn],s[maxn]; ll db(ll x){ return x*x; } int n,m; ll y(int j,int k){ return f[k][j-1]+db(s[k]); } int q[maxn],head,tail=1; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; f[i][1]=s[i]*s[i]; } //以后最后都把第一种情况初始化了！！！！不然调用空的就容易错 for(int j=2;j<=m;j++){//注意j为1也就是只分成一段的情况的初始化！！是s[i]*s[i]!!!!!! tail=head=0; q[tail++]=j-1; for(int i=j;i<=n;i++){ while(head+1<tail&&y(j,q[head+1])-y(j,q[head]) <=2*s[i]*(s[q[head+1]]-s[q[head]]))head++; if(head<tail){ int k=q[head]; f[i][j]=f[k][j-1]+db(s[i]-s[k]); } while(head+1<tail&&(y(j,q[tail-1])-y(j,q[tail-2]))*(s[i]-s[q[tail-1]]) >=(y(j,i)-y(j,q[tail-1]))*(s[q[tail-1]]-s[q[tail-2]]))tail--; q[tail++]=i; } } printf("%lld",f[n][m]*m-db(s[n])); return 0; } 
