【题解】HDU3507 Print Article 斜率优化-chiimo

我水平很菜，你忍一下。

题面

这个题明显的可以定义 $f_i$ 为我打印到 $i$ 点时的最小花费，那么显然我们有 $f_i=\operatorname{min}{f_j+(\sum_{k=j}^i a_k) ^2}, 1\leq j< i$。但是这样做的时间复杂度为 $O(n^2)$ ，不能通过本题。所以考虑斜率优化。

我们先设 $a<b<i$ 且 $f_a+(\sum_{k=a}^i a_k) ^2 < f_b+(\sum_{k=b}^i a_k) ^2$ ，就是说选 $a$ 不选 $b$。然后我们对此式进行一个化简。先设 $sum_i$ 为到 $i$ 的前缀和。

$$
\begin{aligned}
f_a+(\sum_{k=a}^i a_k) ^2 & < f_b+(\sum_{k=b}^i a_k) ^2, \\
f_a+(sum_i-sum_a)^2 & < f_b+(sum_i-sum_b)^2,\\
f_a+sum_i^2-2\times sum_i \times sum_a +sum_a^2 & < f_b+sum_i^2-2\times sum_i \times sum_b +sum_b^2, \\
f_a-2\times sum_i \times sum_a +sum_a^2 & < f_b-2\times sum_i \times sum_b +sum_b^2, \\
f_a-f_b+sum_a^2-sum_b^2 & < 2\times sum_i \times sum_a-2\times sum_i \times sum_b, \\
(f_a+sum_a^2)-(f_b-sum_b^2) & < 2\times sum_i \times (sum_a- sum_b), \\
\frac{(f_a+sum_a^2)-(f_b-sum_b^2)}{sum_a- sum_b} & < 2\times sum_i, \\
\end{aligned}
$$

设 $f_x+sum_x^2$ 为 $Y(x)$ ， $sum_x$ 为 $X(x)$ ，那么
$$\frac{Y(a)-Y(b)}{X(a)-X(b)} < 2 \times sum_i$$

发现了没有，这不就是一个斜率么！

我们继续考虑：

如果 $a,b,c$ 是连续的三个点且保证 $\phi(a,b) > \phi(b,c)$ ，那么我们分类讨论一下：

如果 $\phi(a,b)>2\times sum_i$ ，那么 $a$ 比 $b$ 优。

如果 $\phi(a,b)<2\times sum_i$ ，那么 $\phi(b,c)<2\times sum_i$ ，所以 $c$ 比 $b$ 优。

综上所述， $b$ 废了。我们要把 $b$ 踢出当前列表。

于是我们立马想到用单调队列，很快啊！

然后考虑队头。

如果 $\phi(q_{l+1},q_l)>2\times sum_i$ 那么 $q_l$ 比 $q_{l+1}$ 优，因为我们开的是单调队列，所以 $q_l$ 最优， 用 $q_l$ 进行转移。

否则 $q_{l+1}$ 比 $q_l$ 优，那么很报歉 $q_l$ 废了， 头指针 $+1$ 。

于是这个题就做完了，把上面所有东西拼起来即可，但因为除法有误差，所以我们把所有包含除法的操作进行移项，将分母移到右边去。

代码