Matrix Chain Multiplication
Time Limit : 1 sec, Memory Limit : 65536 KBMatrix-chain Multiplication
The goal of the matrix-chain multiplication problem is to find the most efficient way to multiply given nnmatrices M1,M2,M3,...,MnM1,M2,M3,...,Mn.
Write a program which reads dimensions of MiMi, and finds the minimum number of scalar multiplications to compute the maxrix-chain multiplication M1M2...MnM1M2...Mn.
Input
In the first line, an integer nn is given. In the following nn lines, the dimension of matrix MiMi (i=1...ni=1...n) is given by two integers rr and cc which respectively represents the number of rows and columns of MiMi.
Output
Print the minimum number of scalar multiplication in a line.
Constraints
- 1≤n≤1001≤n≤100
- 1≤r,c≤1001≤r,c≤100
Sample Input 1
630 3535 1515 55 1010 2020 25
Sample Output 1
15125 AC代码：
#define _CRT_SECURE_NO_DEPRECATE#include#include #include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3fconst int N_MAX = 200;int n;int dp[N_MAX][N_MAX];int p[N_MAX];void solve() { for (int i = 1; i <= n;i++) { dp[i][i] = 0; } for (int l = 2; l <= n;l++) { //区间长度由2开始增长 for (int i = 1; i <= n - l + 1;i++) { int j = i + l - 1;//[i,j]为当前需要考虑的区间 dp[i][j] = INF; for (int k = i; k <= j - 1;k++) { //!!!!! dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]); } } } cout << dp[1][n] << endl;}int main() { while (scanf("%d",&n)!=EOF) { for (int i = 1; i <= n;i++) { scanf("%d%d",&p[i-1],&p[i]); } solve(); } return 0;}