Cây Từ Điển Tối Ưu

Buổi 38 — Divide & Conquer DP Dynamic Programming
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ khóa phân biệt được sắp xếp tăng dần từ $1$ đến $N$, khóa thứ $i$ có tần suất truy cập là $f_i$. Bạn cần xây dựng một cây nhị phân tìm kiếm (BST) chứa $N$ khóa này sao cho tổng chi phí tìm kiếm là nhỏ nhất. Chi phí tìm kiếm của khóa thứ $i$ bằng $f_i \times \text{depth}(i)$, trong đó $\text{depth}(i)$ là độ sâu của nút chứa khóa $i$ (gốc có độ sâu $1$).

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 1500$).
  • Dòng thứ hai chứa $N$ số nguyên $f_1, f_2, \dots, f_N$ ($1 \le f_i \le 10^6$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng chi phí tìm kiếm nhỏ nhất có thể.
Ví dụ
Input Output
3
10 12 20
72
4
4 2 6 3
26
Giới hạn
  • $1 \le N \le 1500$
  • $1 \le f_i \le 10^6$
Draft saved