Cây Quyết Định Đoán Số Có Trọng Số
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$
Community Discussion