Chi phí nhảy trạm tối ưu

Buổi 77 — Tổng kết Dynamic Programming
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved