fork download 
  1. #include <iostream>
  2. #define SIZE 505
  3.  
  4. //Matrix Chain Multiplication
  5.  
  6. int dim[ SIZE ], n;
  7.  
  8. long cost[ SIZE ][ SIZE ];
  9.  
  10. void mcm(int n, int dim[ 10 ]) {
  11.  
  12.       int j;
  13.  
  14.       for(int i = 1; i <= n; i++) cost[i][i] = 0;
  15.  
  16.       for(int k = 1; k <= n - 1; ++k)
  17.  
  18.           for(int i = 1; i <= n - k; i++) {
  19.  
  20.                j = i + k;
  21.  
  22.                cost[i][j] = 1LL<<50;
  23.  
  24.                for(int q = i; q <= j - 1; q++) {
  25.  
  26.                  long m = cost[i][q] + cost[q+1][j] + dim[i] * dim[q+1] * dim[j+1];
  27.  
  28.                  if(cost[i][j]>m) {
  29.  
  30.                    cost[i][j] = m;
  31.  
  32.                    cost[j][i] = 1;
  33.                  }
  34.                }
  35.       }
  36.  
  37.       std::cout<<cost[1][n];
  38. }
  39.  
  40. int main(int argc, char const *argv[]) {
  41.  
  42.         //freopen("podm.in","r",stdin);
  43.  
  44.         //freopen("podm.out","w",stdout);
  45.  
  46.  
  47.   std::cin>>n;
  48.  
  49.   for(int i = 1; i <= n + 1; i++) std::cin>>dim[i];
  50.  
  51.   //test: 10 1 10 1 10
  52.   mcm( n, dim);
  53.  
  54.   return 0;
  55. }
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin 
4
10 1 10 1 10
stdout 
120
https://ideone.com/WMqdeW
Matrix Chain Multiplication
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!