Chia Nhóm Dây Chuyền
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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}$
Community Discussion