Cây Quyết Định Đoán Số Có Trọng Số

Binary-search Buổi 63 — Interactive & Constructive Dynamic Programming
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ giá trị có thể có của số bí mật $X$, được đánh số theo thứ tự tăng dần $1, 2, \dots, N$. Để đoán $X$, ở mỗi bước bạn chọn một chỉ số $k$ ($1 \le k \le N$) và trả chi phí $C_k$. Máy chấm sẽ phản hồi ngay lập tức $X < k$, $X = k$ (trò chơi kết thúc), hoặc $X > k$.

Hãy tìm tổng chi phí nhỏ nhất trong trường hợp xấu nhất để chắc chắn tìm được $X$ nếu sử dụng chiến lược thích nghi tối ưu.

Dữ liệu vào
  • Dòng đầu ghi số nguyên $N$ ($1 \le N \le 200$).
  • Dòng thứ hai ghi $N$ số nguyên $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng chi phí tối thiểu trong trường hợp xấu nhất.
Ví dụ
Input Output
3
10 20 30
50
Giới hạn
  • $1 \le N \le 200$
  • $1 \le C_i \le 10^6$
Draft saved