fork download
copy 
  1. #include <iostream>
  2. #include <limits.h>
  3.  
  4. // Матрица Ai имее размерность p[i-1] x p[i] для i = 1..n
  5. int MatrixChainOrder(int p[], int n)
  6. {
  7.     /* Для простоты программы, в m[][] одна дополнительаня строка и
  8.        один дополнительный столбец].  Нулевая строка и нулевой столбец в m[][] не используются */
  9.     int **m = new int* [n];
  10. 	for(int i = 0; i < n; i++)
  11. 		m[i] = new int [n];
  12.  
  13.     int i, j, k, L, q;
  14.  
  15.     /* m[i,j] = минимальное число скалярных умножений, необходимое для вычисления
  16.        матрицы A[i]A[i+1]...A[j] = A[i..j], где размерность A[i] равна
  17.        p[i-1] x p[i] */
  18.  
  19.     // Стоимость равна нулю, когда умножаем одну матрицу
  20.     for (i = 1; i < n; i++)
  21.         m[i][i] = 0;
  22.  
  23.     // L - длина цепочки  
  24.     for (L=2; L<n; L++)   
  25.     {
  26.         for (i=1; i<=n-L+1; i++)
  27.         {
  28.             j = i+L-1;
  29.             m[i][j] = INT_MAX;
  30.             for (k=i; k<=j-1; k++)
  31.             {
  32.                 // q = стоимость/скалярные умножения
  33.                 q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
  34.                 if (q < m[i][j])
  35.                     m[i][j] = q;
  36.             }
  37.         }
  38.     }
  39.  
  40.     return m[1][n-1];
  41. }
  42.  
  43. int main(){
  44. 	const int n = 10;
  45. 	int p[n] = {10, 50, 30, 7, 25, 60, 15, 80, 55, 30};
  46. 	int cost = 0;
  47.  
  48. 	cost = MatrixChainOrder(p, n - 1);
  49.  
  50. 	//std::cout << "Solution for m and s: " << std::endl;
  51.  
  52. 	std::cout << "min cost: " << cost << std::endl;
  53. 	int pause;
  54. 	std::cin >> pause;
  55. }
Runtime error #stdin #stdout 0s 3408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PE8ZnV
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!