#include <iostream>
#include <limits.h>
// Матрица Ai имее размерность p[i-1] x p[i] для i = 1..n
int MatrixChainOrder(int p[], int n)
{
/* Для простоты программы, в m[][] одна дополнительаня строка и
один дополнительный столбец]. Нулевая строка и нулевой столбец в m[][] не используются */
int **m = new int* [n];
for(int i = 0; i < n; i++)
m[i] = new int [n];
int i, j, k, L, q;
/* m[i,j] = минимальное число скалярных умножений, необходимое для вычисления
матрицы A[i]A[i+1]...A[j] = A[i..j], где размерность A[i] равна
p[i-1] x p[i] */
// Стоимость равна нулю, когда умножаем одну матрицу
for (i = 1; i < n; i++)
m[i][i] = 0;
// L - длина цепочки
for (L=2; L<n; L++)
{
for (i=1; i<=n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MAX;
for (k=i; k<=j-1; k++)
{
// q = стоимость/скалярные умножения
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n-1];
}
int main(){
const int n = 10;
int p[n] = {10, 50, 30, 7, 25, 60, 15, 80, 55, 30};
int cost = 0;
cost = MatrixChainOrder(p, n - 1);
//std::cout << "Solution for m and s: " << std::endl;
std::cout << "min cost: " << cost << std::endl;
int pause;
std::cin >> pause;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bGltaXRzLmg+CgovLyDQnNCw0YLRgNC40YbQsCBBaSDQuNC80LXQtSDRgNCw0LfQvNC10YDQvdC+0YHRgtGMIHBbaS0xXSB4IHBbaV0g0LTQu9GPIGkgPSAxLi5uCmludCBNYXRyaXhDaGFpbk9yZGVyKGludCBwW10sIGludCBuKQp7CiAgICAvKiDQlNC70Y8g0L/RgNC+0YHRgtC+0YLRiyDQv9GA0L7Qs9GA0LDQvNC80YssINCyIG1bXVtdINC+0LTQvdCwINC00L7Qv9C+0LvQvdC40YLQtdC70YzQsNC90Y8g0YHRgtGA0L7QutCwINC4CiAgICAgICDQvtC00LjQvSDQtNC+0L/QvtC70L3QuNGC0LXQu9GM0L3Ri9C5INGB0YLQvtC70LHQtdGGXS4gINCd0YPQu9C10LLQsNGPINGB0YLRgNC+0LrQsCDQuCDQvdGD0LvQtdCy0L7QuSDRgdGC0L7Qu9Cx0LXRhiDQsiBtW11bXSDQvdC1INC40YHQv9C+0LvRjNC30YPRjtGC0YHRjyAqLwogICAgaW50ICoqbSA9IG5ldyBpbnQqIFtuXTsKCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJbVtpXSA9IG5ldyBpbnQgW25dOwoKICAgIGludCBpLCBqLCBrLCBMLCBxOwoKICAgIC8qIG1baSxqXSA9INC80LjQvdC40LzQsNC70YzQvdC+0LUg0YfQuNGB0LvQviDRgdC60LDQu9GP0YDQvdGL0YUg0YPQvNC90L7QttC10L3QuNC5LCDQvdC10L7QsdGF0L7QtNC40LzQvtC1INC00LvRjyDQstGL0YfQuNGB0LvQtdC90LjRjwogICAgICAg0LzQsNGC0YDQuNGG0YsgQVtpXUFbaSsxXS4uLkFbal0gPSBBW2kuLmpdLCDQs9C00LUg0YDQsNC30LzQtdGA0L3QvtGB0YLRjCBBW2ldINGA0LDQstC90LAKICAgICAgIHBbaS0xXSB4IHBbaV0gKi8KCiAgICAvLyDQodGC0L7QuNC80L7RgdGC0Ywg0YDQsNCy0L3QsCDQvdGD0LvRjiwg0LrQvtCz0LTQsCDRg9C80L3QvtC20LDQtdC8INC+0LTQvdGDINC80LDRgtGA0LjRhtGDCiAgICBmb3IgKGkgPSAxOyBpIDwgbjsgaSsrKQogICAgICAgIG1baV1baV0gPSAwOwoKICAgIC8vIEwgLSDQtNC70LjQvdCwINGG0LXQv9C+0YfQutC4ICAKICAgIGZvciAoTD0yOyBMPG47IEwrKykgICAKICAgIHsKICAgICAgICBmb3IgKGk9MTsgaTw9bi1MKzE7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGogPSBpK0wtMTsKICAgICAgICAgICAgbVtpXVtqXSA9IElOVF9NQVg7CiAgICAgICAgICAgIGZvciAoaz1pOyBrPD1qLTE7IGsrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgLy8gcSA9INGB0YLQvtC40LzQvtGB0YLRjC/RgdC60LDQu9GP0YDQvdGL0LUg0YPQvNC90L7QttC10L3QuNGPCiAgICAgICAgICAgICAgICBxID0gbVtpXVtrXSArIG1baysxXVtqXSArIHBbaS0xXSpwW2tdKnBbal07CiAgICAgICAgICAgICAgICBpZiAocSA8IG1baV1bal0pCiAgICAgICAgICAgICAgICAgICAgbVtpXVtqXSA9IHE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIG1bMV1bbi0xXTsKfQoKaW50IG1haW4oKXsKCWNvbnN0IGludCBuID0gMTA7CglpbnQgcFtuXSA9IHsxMCwgNTAsIDMwLCA3LCAyNSwgNjAsIDE1LCA4MCwgNTUsIDMwfTsKCWludCBjb3N0ID0gMDsKCgljb3N0ID0gTWF0cml4Q2hhaW5PcmRlcihwLCBuIC0gMSk7CgoJLy9zdGQ6OmNvdXQgPDwgIlNvbHV0aW9uIGZvciBtIGFuZCBzOiAiIDw8IHN0ZDo6ZW5kbDsKCglzdGQ6OmNvdXQgPDwgIm1pbiBjb3N0OiAiIDw8IGNvc3QgPDwgc3RkOjplbmRsOwoJaW50IHBhdXNlOwoJc3RkOjpjaW4gPj4gcGF1c2U7Cn0=