[BZOJ4518/Luogu4072][Sdoi2016]征途(动态规划,斜率优化)

发布于 2018-02-02  190 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4518/Luogu4072][Sdoi2016]征途(动态规划,斜率优化)

Description

Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v,可以证明,v×m^2是一个整数。为了避免精度误差,输出结果时输出v×m^2。

Http

BZOJ
Luogu

Tag

动态规划,斜率优化

解决思路

先考虑答案是怎么算的,设\(Sum[i]\)表示前\(i\)段路的前缀和。
\[Ans=m^2*\frac{\sum_{i=1}^{m} (x_i- \bar x)^2}{m} \\ = m*(\sum_{i=1}^{m} x_{i}^{2}+m* {\bar x}^2-2*\sum_{i=1}^{m} x_i * \bar x) \\ =m*\sum_{i=1}^{m} x_{i}^2+Sum[n]^2-2*Sum[i]^2 \\ = m_{i=1}^{m} x_{i}^2-Sum[n]^2\]
那么这个式子就只与前面\(X_{i}^2\)这一项有关了,把这一项拿出来单独考虑。
设(F[i][j])表示前\(j\)个数分成\(i\)组使得上面那个\(X_{i}^2\)和最小,那么有下面的朴素转移方程
\[F[i][j]=min(F[i-1][k]+(Sum[j]-Sum[j])^2)\]
设\(j1 < j2\),且j2的答案更优,那么有
\[F[i-1][j1]+(Sum[i]-Sum[j1])^2 > F[i-1][j2]+(Sum[i]-Sum[j2])^2 \\ F[i-1][j1]+Sum[j1]^2-F[i-1][j2]-Sum[j2]^2 > 2*Sum[i]*(Sum[j1]-Sum[j2])\]
这样就可以斜率优化了。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4518/Luogu4072][Sdoi2016]征途(动态规划,斜率优化)


HNCJ OIer