Nhân chuỗi ma trận tối ưu

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved