#AT26. Frog 3

Frog 3

[Z] Frog 3(dp_z)

来源: AtCoder Educational DP Contest - Problem Z 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 块石头,编号为 1,2,…,N1, 2, \ldots, N。对于每个 ii(1≤i≤N1 \le i \le N),第 ii 块石头的高度为 hih_i。保证 h1<h2<⋯<hNh_1 < h_2 < \cdots < h_N。

有一只青蛙初始站在石头 11 上。它会重复下面的动作若干次,直到到达石头 NN:

  • 若青蛙当前位于石头 ii,则跳到石头 i+1,i+2,…,Ni+1, i+2, \ldots, N 中的任意一块。若落到石头 jj,需要支付代价 (hj−hi)2+C(h_j - h_i)^2 + C。

求青蛙到达石头 NN 之前所需支付代价总和的最小值。

输入格式

输入由标准输入按以下格式给出:

N C
h_1 h_2 \ldots h_N

输出格式

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

数据范围

  • 输入中的所有值均为整数。
  • 2≤N≤2×1052 \le N \le 2 \times 10^5
  • 1≤C≤10121 \le C \le 10^{12}
  • 1≤h1<h2<⋯<hN≤1061 \le h_1 < h_2 < \cdots < h_N \le 10^6

样例 1

输入:

5 6
1 2 3 4 5

输出:

20

样例 2

输入:

2 1000000000000
500000 1000000

输出:

1250000000000

样例 3

输入:

8 5
1 3 4 5 10 11 12 13

输出:

62