分数: 6 点
警告
2021 年 7 月 17 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
我们有一系列 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 到一些(不一定是连续的)子序列中,同时保持元素的相对顺序。
在这里,让我们定义 总分 作为总和 分数 获得的子序列的 。
找到可能的最小值 总分.
约束
- 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) is 112.
示例输入 3
10 5301 6708 1391 3108 7953 7797 2370 7699 1098 2362 2359
示例输出 3
17095