## 滑雪道（Ski Runs）

> 出題者：Ting
> 難度：4
> 考點：貪心、動態規劃

### Statement

有一座山有 $N$ 個山峰，第 $i$ 個山峰高度為 $h_i$（$1 \leq i \leq N$），山峰之間的高度視為線性。

精通滑雪的 Chung 教授想把這座山規劃為滑雪場，做法是將山峰間的區域劃分為滑雪道和休息區兩種，每個相鄰山峰間可以為滑雪道或休息區，兩種區域會交替出現，例如下圖：


圖中，黑點代表山峰，灰色區域為休息區，其餘顏色均為滑雪道。

不過，設立滑雪道和休息區都具有成本，其中：

- 滑雪道的成本按段計算（連續即視為同一段），一段的成本為其左右兩端的高度差，亦即包含編號 $l$ 到 $r$ 山峰（含端點）的滑雪道造成的成本為 $\lvert h_l - h_r \rvert$。
- 休息區的成本按個計算（連續視為獨立的數個），一個的成本為其左右的山峰中較高者的高度，亦即在編號 $i$ 和 $i + 1$ 山峰間的休息區造成的成本為 $\max(h_i, h_{i + 1})$。

而規劃一座山的總成本即為滑雪道和休息區設立成本的總和。

並且，為了安全考量，每段滑雪道中的高度必須滿足非嚴格單調的條件，亦即若一段滑雪道包含了編號 $l$ 到 $r$ 的山峰，則須滿足 $h_i \leq h_j \space \forall \space l \leq i < j \leq r$ 或 $h_i \geq h_j \space \forall \space l \leq i < j \leq r$ 其一。

Chung 教授想請精通程式設計的你幫忙，計算將給定的山規劃為滑雪場所須的最小成本。

### Input

第一行包含一個數字 $N$，滿足 $2 \leq N \leq 10^6$。

第二行包含 $N$ 個數字 $h_1 \space h_2 \space \dots \space h_N$，滿足 $0 \leq h_i \leq 1000$。

### Output

輸出一個數字表此情況下的最小成本。

### Testcase

- Input

7
1 3 4 2 8 7 5

- Output

18

### Subtask

- Subtask 1 (20%) - $N \leq 16$
- Subtask 2 (80%) - $N \leq 10^6$

### Solution

- Subtask 1

對於每個山峰間為滑雪道或休息區二元枚舉，遍歷檢查非嚴格單調的條件，複雜度為 $\mathcal{O}(2^N \cdot N)$。

或是也可以一邊遞迴枚舉一邊檢查，複雜度為 $\mathcal{O}(2^N)$。

- Subtask 2

定義動態規劃狀態：

- $dp[i][0]$ 表考慮前 $i$ 個山峰，編號 $i$ 和 $i - 1$ 山峰間為休息區或高度為非嚴格遞增時的最小成本。
- $dp[i][1]$ 表考慮前 $i$ 個山峰，編號 $i$ 和 $i - 1$ 山峰間為休息區或高度為非嚴格遞減時的最小成本。

即可按照當前山峰和上一個山峰的高度關係進行轉移，所求為 $\min(dp[n][0], dp[n][1])$。

### Code

- Subtask 1

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e9;

int main() {
    int n;
    cin >> n;

    vector<int> h(n);
    for (int &x: h) cin >> x;

    int ans = MAX;

    for (int i = 0; i < 1 << n - 1; i++) {
        int state = 0, k = 0, now = 0;

        for (int j = 0; j < n - 1; j++) {
            if (i >> j & 1) {
                now += abs(h[j] - h[k]) + max(h[j], h[j + 1]);
                state = 0, k = j + 1;
                continue;
            }
            if ((state == 1 && h[j] > h[j + 1]) ||
                (state == 2 && h[j] < h[j + 1])) {
                now = MAX;
                break;
            }
            if (h[j] != h[j + 1]) state = h[j] < h[j + 1] ? 1 : 2;
        }
        ans = min(ans, now + abs(h[n - 1] - h[k]));
    }

    cout << ans << '\n';

    return 0;
}

- Subtask 2

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> h(n);
    for (int &x: h) cin >> x;

    vector<array<int, 2>> dp(n);

    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i][1] = max(h[i], h[i - 1]) + min(dp[i - 1][0], dp[i - 1][1]);

        if (h[i] >= h[i - 1]) dp[i][0] = min(dp[i][0], dp[i - 1][0] + h[i] - h[i - 1]);
        if (h[i - 1] >= h[i]) dp[i][1] = min(dp[i][1], dp[i - 1][1] + h[i - 1] - h[i]);
    }

    cout << min(dp[n - 1][0], dp[n - 1][1]) << '\n';

    return 0;
}