分数: 100 点
问题陈述
有 N 石头,编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N), 石头的高度 i is h_i。 在这里, h_1 < h_2 < \cdots < h_N 成立。
有一只青蛙最初在石头上 1。 他会重复以下动作多次才能到达斯通 N:
- 如果青蛙当前位于石头上 i,跳转到以下选项之一:Stone i + 1, i + 2, \ldots, N。这里,成本为 (h_j - h_i)^2 + C 正在开始,其中 j 是着陆的石头。
找出青蛙到达石头之前开始的最小可能总成本 N.
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 2 \times 10^5
- 1 \leq C \leq 10^{12}
- 1 \leq h_1 < h_2 < \cdots < h_N \leq 10^6
输入
输入由标准输入按以下格式给出:
N C h_1 h_2 \ldots h_N
输出
打印可能产生的最小总成本。
示例输入 1
5 6 1 2 3 4 5
示例输出 1
20
如果我们沿着这条路走 1 → 3 → 5,总成本将开始 ((3 - 1)^2 + 6) + ((5 - 3)^2 + 6) = 20.
示例输入 2
2 1000000000000 500000 1000000
示例输出 2
1250000000000
答案可能不适合 32 位整数类型。
示例输入 3
8 5 1 3 4 5 10 11 12 13
示例输出 3
62
如果我们沿着这条路走 1 → 2 → 4 → 5 → 8,总成本将开始 ((3 - 1)^2 + 5) + ((5 - 3)^2 + 5) + ((10 - 5)^2 + 5) + ((13 - 10)^2 + 5) = 62.