← 返回题目列表

AtCoder · past202107_m

M. 划分

中文机器翻译题面 查看原题

分数: 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