/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
長さ N の整数列 A=(A_1, A_2, \dots ,A_N) と整数 C があります。
長さ K\ (K \geq 1) の整数列 B=(B_1, B_2, \dots ,B_K) の スコア を、以下の式で定義します。
\displaystyle C + \sum_{i=1}^{K-1} |B_{i+1} - B_i|
整数列 A を順序を保ったまま、いくつかの（連続するとは限らない）部分列に分解します。
このとき整数列 A の 合計スコア を、得られた整数列の スコア の総和として定義します。
整数列 A の 合計スコア の最小値を求めてください。
制約
- 1 \leq N \leq 200
- 1 \leq C \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C A_1 A_2 \dots A_N
出力
合計スコア の最小値を出力せよ。
入力例 1
6 10 4 25 1000000000 9 19 22
出力例 1
44
(4, 9), (25, 19, 22), (1000000000) と分解します。それぞれの スコア は 15, 19, 10 です。
入力例 2
5 100 3 1 4 1 5
出力例 2
112
(3, 1, 4, 1, 5) の スコア は 112 です。
入力例 3
10 5301 6708 1391 3108 7953 7797 2370 7699 1098 2362 2359
出力例 3
17095
Score : 6 points
Warning
Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have a sequence of N integers A=(A_1, A_2, \dots ,A_N) and an integer C.
Let us define the score of the sequence of K\ (K \geq 1) integers B=(B_1, B_2, \dots ,B_K) as the following:
\displaystyle C + \sum_{i=1}^{K-1} |B_{i+1} - B_i|.
We will decompose the sequence A into some (not necessarily contiguous) subsequences while keeping the relative order of the elements.
Here, let us define the total score as the sum of the scores of the subsequences obtained.
Find the minimum possible total score.
Constraints
- 1 \leq N \leq 200
- 1 \leq C \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C A_1 A_2 \dots A_N
Output
Print the minimum possible value of the total score.
Sample Input 1
6 10 4 25 1000000000 9 19 22
Sample Output 1
44
We should divide it into (4, 9), (25, 19, 22), (1000000000). Their scores are 15, 19, 10, respectively.
Sample Input 2
5 100 3 1 4 1 5
Sample Output 2
112
The score of (3, 1, 4, 1, 5) is 112.
Sample Input 3
10 5301 6708 1391 3108 7953 7797 2370 7699 1098 2362 2359
Sample Output 3
17095