| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
NTMULMAT - Multiply Matrixs |
Given N matrices A1, A2 ... An, the matrix whose size is di – 1 × di. Determine the multiplication matrix matrix A1.A2 ... An such that the number of multiplications to perform is minimal.
Input
The first line contains a positive integer n; 1 <= n <= 100.
The second line contains n + 1 integers d0, d1, d2, ..., dn; 2 <= d_i <= 100
Output
A single integer is the least number of multiplications to use
Multiplying a matrix of size m × n by an matrix of n × p, the number of multiplications to use is m.n.p.
On the other hand, multiplication of matrices is coherent, that is: (A.B) .C = A. (B.C). Therefore in different sequences, each determines the number of multiplications to use.
Given N matrices A1, A2 ... An, the size of A_i matrix is d_(i – 1) × di. Determine the minimal multiplication to using for multiplying n matrixs A1, A2 ... An .
Input
The first line contains a positive integer n; 1 <= n <= 100.
The second line contains n + 1 integers d0, d1, d2, ..., dn; 2 <= d_i <= 100
Output
A single integer is the least number of multiplications to use.
Example
Input:
6
3 3 3 4 2 2 3
Output
90
| Được gửi lên bởi: | Phong NT |
| Ngày: | 2020-02-12 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | C++ 4.3.2 CPP CPP14 PAS-FPC |
RSS