Bậc Đá Tối Ưu · canuc80k1200 · Thuật toán Canuc80k

Có $N$ bậc đá được đánh số từ $1$ đến $N$ ; bậc $i$ có độ cao $h_{i}$ . Một robot bắt đầu ở bậc $1$ . Từ bậc $i$ , robot được chuyển đến bậc $i + 1$ hoặc $i + 2$ nếu bậc đó tồn tại. Mỗi lần chuyển từ $i$ sang $j$ tốn $∣ h_{i} - h_{j} ∣$ đơn vị năng lượng. Hãy tìm tổng năng lượng nhỏ nhất để robot đến bậc $N$ .

Input

Dòng đầu chứa số nguyên $N$ .
Dòng thứ hai chứa $N$ số nguyên $h_{1}, h_{2}, \dots, h_{N}$ .

Output

In một số nguyên là tổng chi phí nhỏ nhất để đến bậc $N$ .

Constraints

$2 \leq N \leq 1 0^{5}$ .
$1 \leq h_{i} \leq 1 0^{4}$ với mọi $i$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 12$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

5
8 13 4 10 7

Output

Giải thích: Có thể đi qua các bậc $1 \to 3 \to 5$ , tốn $∣8 - 4∣ + ∣4 - 7∣ = 7$ . Mọi đường đi khác đều có tổng chi phí không nhỏ hơn.

Ý tưởng: Đặt dp[i] là tổng năng lượng nhỏ nhất để đến bậc i. Ta có dp[1]=0, dp[2]=|h_2-h_1|; với i≥3:
Ý tưởng: dp[i] = min(dp[i-1] + |h_i-h_{i-1}|, dp[i-2] + |h_i-h_{i-2}|).
Chứng minh tính đúng đắn: Ta chứng minh bằng quy nạp theo i. Hai giá trị cơ sở đúng trực tiếp. Với i≥3, bước cuối của mọi đường đi tới i phải xuất phát từ đúng một trong hai bậc i-1 hoặc i-2. Theo giả thiết quy nạp, chi phí tốt nhất để tới mỗi bậc tiền nhiệm lần lượt là dp[i-1] và dp[i-2]; cộng chi phí bước cuối rồi lấy giá trị nhỏ hơn vì thế xét đủ mọi đường đi và chọn đúng đường có chi phí nhỏ nhất. Do đó dp[N] là đáp án.
Độ phức tạp: Thời gian O(N) và bộ nhớ O(N).