征途

未分类

用$a_i$表示没天走的路程，$s_i$表示$a_i$的前缀和
得到式子
$ans=m^2*{1\over m}[\sum\limits_{i=1}^m (a_i-{s_n\over m})^2]$
展开化简得到
$=m(\sum\limits_{i=1}^ma_i^2+{s_n^2\over m}-{2s_n\sum\limits_{i=1}^ma_i\over m})$
$=m\sum\limits_{i=1}^m{a_i}^2-{s_n}^2$
发现式子至于$a_i ^{2}$有关
就是将n个数划分成m个部分然后让这些部分的平方和最小
令$dp(i,j)$表示前i个数划分了j次的最小花费
那么枚举k $dp(i,j)=min\{{dp(i-1,k)+{(s_j-s_k)}^2}\}$
把上面的式子展开得到
$dp(i,j)=min\{-2s_ks_j+dp(i-1,k)+s_k^2+s_j^2\}$
然后你可以滚掉一维 没用