Chi phí nhảy trạm tối ưu
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ trạm năng lượng xếp thành hàng ngang, đánh số từ $1$ đến $N$. Mỗi trạm $i$ có hai tham số $a_i$ và $b_i$. Bạn bắt đầu tại trạm $1$ với chi phí ban đầu bằng $0$ và muốn di chuyển đến trạm $N$.
Từ trạm $j$ ($j < i$), bạn có thể nhảy trực tiếp đến trạm $i$ với chi phí nhảy là $(a_i - a_j)^2 + C$, trong đó $C$ là hằng số cho trước. (Không bắt buộc $a_i$ tăng dần).
Hãy tìm tổng chi phí nhỏ nhất để đi từ trạm $1$ đến trạm $N$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, C$ ($2 \le N \le 10^5$, $0 \le C \le 10^9$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($|a_i| \le 10^6$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 5 2 4 |
14 |
Giới hạn
- $2 \le N \le 10^5$
- $0 \le C \le 10^9$, $|a_i| \le 10^6$
Community Discussion