根号分治

January 6, 2023 • Comment

Description

给定序列 $a_{1}, a_{2}, \dots, a_{n}$ 。

每次操作可以从 $i$ 跳到 $j$ ，费用为 $min {a_{i}, a_{i + 1}, \dots, a_{j}} \times (j - i)^{2}$ 。

对于每个 $k, 1 \leq k \leq n$ ，求出从 $1$ 到达 $k$ 的最小费用。