Cây Tìm Kiếm Mở Rộng

Buổi 38 — Divide & Conquer DP Dynamic Programming
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved