Nhân chuỗi ma trận tối ưu
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ ma trận $M_1, M_2, \dots, M_N$, trong đó ma trận $M_i$ có kích thước $d_{i-1} \times d_i$. Phép nhân hai ma trận kích thước $a \times b$ và $b \times c$ tiêu tốn $a \cdot b \cdot c$ phép nhân vô hướng. Hãy tìm số phép nhân vô hướng ít nhất để tính tích $M_1 M_2 \cdots M_N$.
Cấu trúc con tối ưu: $dp[l][r] = \min_{l \le k < r} (dp[l][k] + dp[k+1][r] + d_{l-1} \cdot d_k \cdot d_r)$.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên $N$. Dòng thứ hai chứa $N+1$ số nguyên $d_0, d_1, \dots, d_N$.
Dữ liệu ra
Một số nguyên duy nhất là số phép nhân vô hướng ít nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 10 30 5 60 |
4500 |
| 4 40 20 30 10 30 |
26000 |
Giới hạn
$1 \le N \le 400$, $1 \le d_i \le 1000$.
Community Discussion