Frog 3
题意翻译
有 $N$ 个石头,编号为 $1,2,\dots,N$,第 $i$ 个高为 $h_i$。保证 $h$ 严格单调递增。
有一只青蛙在第一个石头上,它可以跳到石头编号为 $i+1,i+2,\dots,N$。当他跳到编号 $j$ 石头时的花费是
$(h_i-h_j)^2+C$。求跳到编号为 $N$ 石头的最小花费。
题目描述
[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_z
$ 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
5 6
1 2 3 4 5
输出样例 #1
20
输入样例 #2
2 1000000000000
500000 1000000
输出样例 #2
1250000000000
输入样例 #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 $
### Sample Explanation 1
足場 $ 1 $ → $ 3 $ → $ 5 $ と移動すると、コストの総和は $ ((3\ -\ 1)^2\ +\ 6)\ +\ ((5\ -\ 3)^2\ +\ 6)\ =\ 20 $ となります。
### Sample Explanation 2
答えは 32-bit 整数型に収まらない場合があります。
### Sample Explanation 3
足場 $ 1 $ → $ 2 $ → $ 4 $ → $ 5 $ → $ 8 $ と移動すると、コストの総和は $ ((3\ -\ 1)^2\ +\ 5)\ +\ ((5\ -\ 3)^2\ +\ 5)\ +\ ((10\ -\ 5)^2\ +\ 5)\ +\ ((13\ -\ 10)^2\ +\ 5)\ =\ 62 $ となります。