TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5642
  • 問題
  • P5642【SNOI2019 day1】通信
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 4s,512m
    問題説明

    \(n\) 个排成一列的哨站要进行通信。第 \(i\) 个哨站的频段为 \(a_i\)

    每个哨站 \(i\) 需要选择以下二者之一:

    1. 直接连接到控制中心,代价为 \(W\)
    2. 连接到前面的某个哨站 \(j(j<i)\),代价为 \(\lvert a_i - a_j \rvert\)

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

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

    入力形式

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

    第 $2$ 行 \(n\) 个由空格分隔的自然数 \(a_1, a_2, \dots , a_n\) 依次表示每个哨站的频段。

    出力形式

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

    サンプル入力 1

    6 7
    8 4 6 1 3 0

    サンプル出力 1

    23

    サンプル入力 2

    8 4
    0 4 2 6 1 5 3 7

    サンプル出力 2

    18

    ヒント

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

    • 对于 $10%$ 的数据,\(n\le 10\)
    • 对于另外 $10%$ 的数据,\(n\le 20\)
    • 对于另外 $20%$ 的数据,\(n\le 50,W\le 5,a_i\le 4\)
    • 对于另外 $20%$ 的数据,\(n\le 100\)
    • 对于另外 $20%$ 的数据,\(n\le 300\)
    • 对于余下 $20%$ 的数据,无特殊限制。

    样例解释 1

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

    点此下载大样例