AT_dp_z Frog 3

题目描述

有 $N$ 个台阶。每个台阶编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N$），第 $i$ 个台阶的高度为 $h_i$。已知 $h_1 < h_2 < \cdots < h_N$。

一只青蛙最初在台阶 $1$ 上。青蛙可以多次进行如下操作，试图到达台阶 $N$：

• 当青蛙在台阶 $i$ 时，可以跳到台阶 $i+1, i+2, \ldots, N$ 中的任意一个。若跳到台阶 $j$，则需要支付的代价为 $(h_j - h_i)^2 + C$。

请你求出青蛙到达台阶 $N$ 所需支付的总代价的最小值。

输入格式

输入以如下格式从标准输入给出。

$N$ $C$ $h_1$ $h_2$ $\ldots$ $h_N$

输出格式

输出青蛙所需支付的总代价的最小值。

输入输出样例 #1

输入 #1

5 6
1 2 3 4 5

输出 #1

20

输入输出样例 #2

输入 #2

2 1000000000000
500000 1000000

输出 #2

1250000000000

输入输出样例 #3

输入 #3

8 5
1 3 4 5 10 11 12 13

输出 #3

62

说明/提示

限制条件

• 所有输入均为整数。
• $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$

样例解释 1

若青蛙依次跳到台阶 $1 \to 3 \to 5$，总代价为 $((3-1)^2 + 6) + ((5-3)^2 + 6) = 20$。

样例解释 2

答案可能超出 32 位整数范围。

样例解释 3

若青蛙依次跳到台阶 $1 \to 2 \to 4 \to 5 \to 8$，总代价为 $((3-1)^2 + 5) + ((5-3)^2 + 5) + ((10-5)^2 + 5) + ((13-10)^2 + 5) = 62$。

由 ChatGPT 4.1 翻译