我水平很菜,你忍一下。

题面

这个题明显的可以定义 $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$ 。

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

代码

分类: 文章

Chiimo

菜.

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code