Chia Nhóm Dây Chuyền

Buổi 37 — Convex Hull Trick Dynamic Programming
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một dây chuyền sản xuất gồm $N$ công đoạn đánh số từ $1$ đến $N$. Bạn cần hoàn thành tất cả các công đoạn với chi phí tối thiểu.

Đặt $dp[i]$ là tổng chi phí nhỏ nhất để hoàn thành đến công đoạn $i$ (với $dp[0] = 0$). Với mỗi $i$ ($1 \le i \le N$), bạn có thể chuyển trực tiếp từ một trạng thái $j$ ($0 \le j < i$) sang $i$ theo công thức: \[dp[i] = \min_{0 \le j < i} \left( dp[j] + a_i \cdot b_j \right) + c_i\]

Biết rằng dãy $a_1 \le a_2 \le \dots \le a_N$ không giảm và dãy $b_0 > b_1 > \dots > b_{N-1}$ giảm ngặt. Hãy tìm giá trị $dp[N]$.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^6$).
  • Dòng thứ ba chứa $N$ số nguyên $b_0, b_1, \dots, b_{N-1}$ ($0 \le b_j \le 10^9$).
  • Dòng thứ tư chứa $N$ số nguyên $c_1, c_2, \dots, c_N$ ($0 \le c_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là giá trị $dp[N]$.
Ví dụ
Input Output
3
1 2 3
5 3 1
2 1 4
18
Giới hạn
  • $1 \le N \le 10^5$
  • $a_1 \le a_2 \le \dots \le a_N$, $b_0 > b_1 > \dots > b_{N-1}$
Draft saved