Nhảy cột tối ưu chi phí (Convex Hull Trick)

Buổi 37 — Convex Hull Trick Buổi 69-70 — Mock Tổng hợp Dynamic Programming
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ chiếc cột xếp thành hàng, chiều cao các cột theo thứ tự không giảm: $H_1 \le H_2 \le \dots \le H_N$. Bạn bắt đầu ở cột $1$ và muốn nhảy đến cột $N$. Từ cột $j$, bạn có thể nhảy tới cột $i$ ($j < i$) với chi phí $(H_i - H_j)^2 + C$. Hãy tìm tổng chi phí nhỏ nhất để đi từ cột $1$ đến cột $N$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, C$.
  • Dòng thứ hai chứa $N$ số nguyên $H_1, H_2, \dots, H_N$.
Dữ liệu ra

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ
Input Output
5 6
1 2 3 4 5
20
Giới hạn

$2 \le N \le 2 \cdot 10^5$, $1 \le C \le 10^{12}$, $1 \le H_1 \le H_2 \le \dots \le H_N \le 10^6$.

Draft saved