Cây Tìm Kiếm Mở Rộng
Đề bài
Cho $N$ khóa $K_1 < K_2 < \dots < K_N$ cùng tần suất tìm thấy $p_1, p_2, \dots, p_N$, và $N+1$ khoảng trống $D_0, D_1, \dots, D_N$ (với $D_0$ nhỏ hơn $K_1$, $D_i$ nằm giữa $K_i$ và $K_{i+1}$, $D_N$ lớn hơn $K_N$) có tần suất tìm kiếm thất bại là $q_0, q_1, \dots, q_N$. Khi xây dựng cây nhị phân tìm kiếm mở rộng (nút trong chứa khóa $K_i$, lá ngoài chứa khoảng trống $D_j$), chi phí tìm kiếm một nút bằng tần suất của nó nhân với độ sâu (gốc có độ sâu $1$, lá ngoài ở độ sâu của nút cha cộng $1$, tức nếu nút trong có độ sâu $d$ thì con lá của nó có độ sâu $d+1$, nhưng trong bài này ta định nghĩa chi phí nút lá $D_j$ ở mức $d$ là $q_j \cdot d$ với mức gốc là $0$, tức $dp[i][j] = w(i, j) + \min_{i \le k \le j}(dp[i][k-1] + dp[k+1][j])$ và $dp[i][i-1] = 0$). Hãy tìm tổng chi phí nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 2000$).
- Dòng thứ hai chứa $N$ số nguyên $p_1, p_2, \dots, p_N$ ($1 \le p_i \le 10^6$).
- Dòng thứ ba chứa $N+1$ số nguyên $q_0, q_1, \dots, q_N$ ($1 \le q_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 |
|---|---|
| 3 10 12 20 5 4 3 2 |
100 |
| 2 5 10 2 3 4 |
34 |
Giới hạn
- $1 \le N \le 2000$
- $1 \le p_i, q_i \le 10^6$
Community Discussion