#PQJ61x356. QOJ 61_356

    ID: 3018 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2019动态规划

QOJ 61_356

nn 个排成一列的哨站要进行通信。第 ii 个哨站的频段为 aia_i。

每个哨站 ii 需要选择以下二者之一:

直接连接到控制中心,代价为 WW;

连接到前面的某个哨站 jj(j<ij< i),代价为 ∣ai−aj∣\lvert a_i - a_j \rvert。

每个哨站只能被后面的至多一个哨站连接。

请你求出最小可能的代价和。

输入格式

第 11 行两个自然数 n,Wn, W,分别表示哨站个数和连接到控制中心的代价;

第 22 行 nn 个由空格分隔的自然数 a1,a2,…,ana_1, a_2, \dots , a_n 依次表示每个哨站的频段。

输出格式

输出 11 行 11 个自然数表示答案。

样例数据

样例 1 输入

6 7 8 4 6 1 3 0

样例 1 输出

23

样例 1 解释

如果用 00 表示控制中心,最优方案中每个哨站向前连接的哨站依次为 0,0,1,2,3,40,0,1,2,3,4。

样例 2 输入

8 4 0 4 2 6 1 5 3 7

样例 2 输出

18

子任务

对于所有数据,1≤n≤1000,0≤w,ai≤1091\le n \le 1000,0\le w,a_i\le 10^9。

对于 10%10\% 的数据,n≤10n\le 10;

对于另外 10%10\% 的数据,n≤20n\le 20;

对于另外 20%20\% 的数据,n≤50,W≤5,ai≤4n\le 50,W\le 5,a_i\le 4;

对于另外 20%20\% 的数据,n≤100n\le 100;

对于另外 20%20\% 的数据,n≤300n\le 300;

对于余下 20%20\% 的数据,无特殊限制。