Реализации алгоритмов/Задача о перемножении цепочки матриц
Реализация задачи о перемножении цепочки матриц на разных языках программирования.
#include <iostream>
#include <vector>
using namespace std;
const int INT_INF = 1e7+3;
void print_optimal_parens(vector<vector<int>> &s, int i, int j)
{
if(i == j) cout<<"A_i";
else {
cout<<"(";
print_optimal_parens(s, i, s[i][j]);
print_optimal_parens(s, s[i][j] + 1, j);
cout<<")";
}
}
int main() {
vector<int> p;
int p_cur;
while(cin>>p_cur) p.push_back(p_cur);
int n = p.size() - 1;
vector<vector<int>> m(n + 1, vector<int> (n + 1, INT_INF));
vector<vector<int>> s(n + 1, vector<int> (n + 1, INT_INF));
for(int i = 1; i <= n; i++) m[i][i] = 0; //минимальное количество скалярных умножений матрицы самой на себя 0
for(int l = 2; l <= n; l++) { //длина цепочки
for(int i = 1; i <= (n - l + 1); i++) {
int j = i + l - 1;
m[i][j] = INT_INF;
for(int k = i; k <= (j - 1); k++) {
int q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];
if (q < m[i][j]) {
m[i][j] = q;
} else {
m[i][j] = q;
s[i][j] = k;
}
}
}
}
//Ответ
cout<<m[1][n]<<"\n";
//Восстановление ответа
print_optimal_parens(s, 1, n);
}