Advertisement
ambition-xx

MatrixChain

Nov 12th, 2020
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. const int num = 4; //矩阵个数
  4. //输入矩阵链的向量
  5. int p[num+1]={10, 30, 20, 10, 200};
  6. //int p[num+1]={30, 35, 15, 5, 10, 20};
  7. //初始化
  8. int m[num+1][num+1] = {0}, s[num+1][num+1] = {0};
  9. int main(){
  10.     //r表示步长
  11.     for(int r = 2; r <= num; r++){
  12.         //i表示起始位置
  13.         for(int i = 1; i <= num - r + 1; i++){
  14.             int j = i + r - 1; //计算终点位置
  15.             m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
  16.             s[i][j] = i;
  17.             // 枚举从i到j中间每一个可能的划分位置
  18.             for(int k = i + 1; k <= j - 1; k++){
  19.                 int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
  20.                 if ( t < m[i][j] ) {
  21.                     m[i][j] = t;
  22.                     s[i][j] = k;
  23.                 }
  24.             }
  25.         }
  26.     }  
  27.     cout<<m[1][num];
  28.     return 0;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement