---

1. 题意理解

有 $n$ 个哨站，第 $i$ 个哨站的频段是 $a_i$。

每个哨站 $i$ 可以：

1. 直接连到控制中心，代价 $W$。
2. 连到前面的某个哨站 $j$（$j < i$），代价 $|a_i - a_j|$。

限制：每个哨站只能被至多一个后面的哨站连接（即每个哨站作为父节点最多一个子节点）。

要求总代价最小。

---

2. 问题结构分析

这其实是一个树形结构：控制中心是根节点（节点 $0$），哨站 $1 \dots n$ 是子节点。
每个哨站要么是根的直接孩子（代价 $W$），要么是某个前面哨站的孩子（代价 $|a_i-a_j|$）。

由于“每个哨站只能被后面的至多一个哨站连接”，意味着如果我们把哨站按 $1 \dots n$ 排列，连接关系形成若干条链（每个链的尾部是某个哨站，它后面没有连它）。

---

3. 动态规划思路

设 $dp[i]$ 表示考虑前 $i$ 个哨站，且第 $i$ 个哨站是它所在链的最后一个节点（即没有被后面的哨站连接）时，前 $i$ 个哨站的最小总代价。

那么转移时，我们考虑第 $i$ 个哨站所在的链：

• 可能第 $i$ 个哨站直接连控制中心：代价 $W$。
• 可能第 $i$ 个哨站连到前面的某个哨站 $j$（$j < i$），那么 $j$ 到 $i$ 之间的所有哨站（$j+1, \dots, i-1$）必须自己作为链尾（即它们各自要么连控制中心，要么连更前面的哨站，但不会连到 $j$ 到 $i$ 之间的哨站，因为 $i$ 是链尾）。

所以我们可以枚举链的起点 $k$（$1 \le k \le i$），表示从 $k$ 到 $i$ 形成一条链，链头 $k$ 连控制中心（代价 $W$），链中 $k+1$ 连 $k$，$k+2$ 连 $k+1$，…，$i$ 连 $i-1$，这条链的总代价为：

$$W + \sum_{t=k}^{i-1} |a_{t+1} - a_t|$$

前 $k-1$ 个哨站的最小代价是 $dp[k-1]$（$k-1$ 是链尾）。

特殊情况：$k=1$ 时，$dp[0] = 0$（没有哨站，代价 0）。

---

4. 状态转移方程

因此：

$$dp[i] = \min_{1 \le k \le i} \left\{ dp[k-1] + W + \sum_{t=k}^{i-1} |a_{t+1} - a_t| \right\} $$

初始：$dp[0] = 0$。

答案：$dp[n]$。

---

5. 复杂度优化

直接计算是 $O(n^3)$（$i$ 从 $1$ 到 $n$，$k$ 从 $1$ 到 $i$，求和又是 $O(n)$），对于 $n \le 1000$ 可能太慢。

我们可以预处理差分绝对值的前缀和来优化：

设

$$diff[t] = |a_{t+1} - a_t| \quad (1 \le t \le n-1)$$ $$pref[i] = \sum_{t=1}^{i} diff[t]$$

那么

$$\sum_{t=k}^{i-1} |a_{t+1} - a_t| = pref[i-1] - pref[k-1] $$

于是转移变成：

$$dp[i] = \min_{1 \le k \le i} \left\{ dp[k-1] + W + pref[i-1] - pref[k-1] \right\} $$

即：

$$dp[i] = pref[i-1] + W + \min_{1 \le k \le i} \left\{ dp[k-1] - pref[k-1] \right\} $$

我们可以在遍历 $i$ 时维护 $\min_{1 \le k \le i} (dp[k-1] - pref[k-1])$，这样转移就是 $O(1)$。

总复杂度 $O(n)$。

---

6. 正确性验证

样例 1
$n=6, W=7$
$a = [8,4,6,1,3,0]$

计算 $diff$：
$|4-8|=4, |6-4|=2, |1-6|=5, |3-1|=2, |0-3|=3$
$pref = [4, 6, 11, 13, 16]$（下标从 1 开始）

$dp[0] = 0$
$dp[1] = pref[0] + W + \min\{ dp[0]-pref[0] \}$
$pref[0]=0$，$\min\{0-0\}=0$
$dp[1] = 0 + 7 + 0 = 7$

$dp[2]$：
$pref[1]=4$，$\min\{0, 7-0\}=0$
$dp[2] = 4 + 7 + 0 = 11$

$dp[3]$：
$pref[2]=6$，$\min\{0, 7-0, 11-4\} = \min\{0,7,7\}=0$
$dp[3] = 6 + 7 + 0 = 13$

$dp[4]$：
$pref[3]=11$，$\min\{0,7,7,13-6\}=\min\{0,7,7,7\}=0$
$dp[4] = 11 + 7 + 0 = 18$

$dp[5]$：
$pref[4]=13$，$\min\{0,7,7,7,18-11\}=\min\{0,7,7,7,7\}=0$
$dp[5] = 13 + 7 + 0 = 20$

$dp[6]$：
$pref[5]=16$，$\min\{0,7,7,7,7,20-13\}=\min\{0,7,7,7,7,7\}=0$
$dp[6] = 16 + 7 + 0 = 23$

输出 $23$，符合样例。

---

7. 代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long W;
    cin >> n >> W;
    vector<long long> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<long long> diff(n+1, 0);
    vector<long long> pref(n+1, 0);
    for (int i = 1; i <= n-1; i++) {
        diff[i] = abs(a[i+1] - a[i]);
        pref[i] = pref[i-1] + diff[i];
    }
    
    vector<long long> dp(n+1, 0);
    long long min_val = 0; // dp[0] - pref[0] = 0 - 0 = 0
    
    for (int i = 1; i <= n; i++) {
        dp[i] = pref[i-1] + W + min_val;
        min_val = min(min_val, dp[i] - pref[i]);
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

---

8. 总结

这道题的关键在于：

1. 将问题转化为链式连接，定义 $dp[i]$ 为前 $i$ 个哨站且第 $i$ 个是链尾的最小代价。
2. 通过枚举链的起点，得到转移方程。
3. 利用前缀和优化，将复杂度从 $O(n^3)$ 降到 $O(n)$。

最终算法非常高效，可以处理 $n \le 10^6$ 的规模，而题目只到 $n \le 1000$，绰绰有余。