#176. Nhân chuỗi ma trận (MCMULTI)

Cho một dãy gồm ma trận . Kích thước của ma trận là . Tìm số phép nhân vô hướng tối thiểu cần thiết để tính tích của các ma trận này. Phép nhân ma trận có tính kết hợp, ví dụ , nhưng số phép toán có thể khác nhau.

Biết rằng để nhân một ma trận kích thước với một ma trận kích thước , cần phép nhân vô hướng.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên .
• Dòng thứ hai chứa số nguyên .

Kết quả: In ra một số nguyên duy nhất là số phép nhân vô hướng tối thiểu.

Ví dụ:

Dữ liệu:

3
10 20 30 40

Kết quả:

18000

Giải thích: Các ma trận là , , .

• Cách 1: . Chi phí = .
• Cách 2: . Chi phí = .

Chi phí tối thiểu là 18000.

Giới hạn: