AC. 梦想

frank_c1

[SDOI 2016] 征途

发布于2016年04月23日 | 暂无评论 | 2,601阅读 | 动态规划,斜率优化

题目描述

Pine 开始了从 S 地到 T 地的征途。

从 S 地到 T 地的路可以划分成n段,相邻两段路的分界点设有休息站。

Pine 计划用m天到达 T 地。除第m天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。

Pine 希望每一天走的路的长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。帮助 Pine 求出方差最小是多少。

设方差是v,可以证明,v \times m ^2是一个整数。为了避免精度误差,输出结果时输出v \times m ^ 2

输入格式

第一行两个数n,m

第二行n个数,表示n段路的长度。

输出格式

一个数,最小方差乘以m ^ 2后的值。

题目解析

简单的斜率优化动态规划。

题目要求优化的是方差。方差的计算公式比较复杂,难以直接优化,我们先化简一下。设m是天数,a_i是第i天走的路程,xm天走的路程的平均值,则有

\begin{aligned} ans & = m^2 v \\ & = m ^ 2 \frac{1} {m} \sum_{i=1} ^ {m} {(a_i - x) ^ 2} \\ & = m (\sum_{i=1} ^ {m} {a_i ^ 2} - 2 x \sum_{i=1} ^ {m} {a_i} + m x ^ 2) \\ & = m \sum_{i=1} ^ {m} {a_i ^ 2} - 2 m \frac{1} {m} \sum_{i=1} ^ {m} {a_i} \sum_{i=1} ^ {m} {a_i} + m^2 \frac{1} {m^2} (\sum_{i=1} ^ {m} {a_i}) ^ 2 \\ & = m \sum_{i=1} ^{m} {a_i ^ 2} - (\sum_{i=1} ^{m} {a_i}) ^ 2 \\ & = m \sum_{i=1} ^ {m} {a_i ^ 2} - n ^ 2 \end{aligned}

于是我们只需要最小化\sum_{i=1} ^ {m} {a_i ^ 2}即可。令S(i)为第i个休息点距出发点的距离,dp(i,j)为前i天走前j段路所需的代价。则有

dp(i,j) = \min_{k=0} ^ {j-1} {dp(i-1,k) + (S(j) - S(k)) ^ 2}

显然这个式子时可以用斜率优化的。首先我们可以以i - j顺序递推,令f(k) = dp(i-1,k)。对于两个决策点j,k,若jk优,则有

\begin{aligned} f(j) + (S(i) - S(j)) ^ 2 & \lt f(k) + (S(i) - S(k)) ^ 2 \Rightarrow \\ f(j) + S(i) ^ 2 - 2S(i)S(j) + S(j) ^ 2 & \lt f(k) + S(i) ^ 2 - 2S(i)S(k) + S(k) ^ 2 \Rightarrow \\ f(j) - f(k) + S(j) ^ 2 - S(k) ^ 2 & \lt 2S(i)(S(j) - S(k)) \end{aligned}

U(j,k) = f(j) - f(k) + S(j) ^ 2 - S(k) ^ 2,D(j,k) = 2(S(j) - S(k)),则jk优当且仅当

\frac{U(j,k)} {D(j,k)} \lt S(i)

于是就解决啦。时间复杂度O(nm)。递推时可以滚动数组,空间复杂度O(n)