# Untitled

unknown
plain_text
a year ago
2.5 kB
2
Indexable
Never
```#include <iostream>
#include <vector>
#include <climits>

// Function to print the optimal parenthesized sequence order
void printParenthesis(int i, int j, std::vector<std::vector<int>>& bracket, char& name)
{
// Base case: when there is only one matrix in the chain
if (i == j)
{
std::cout << name++;
return;
}

std::cout << "(";

// Recursively print optimal parenthesized sequence order
// for matrices from i to bracket[i][j]
printParenthesis(i, bracket[i][j], bracket, name);

// Recursively print optimal parenthesized sequence order
// for matrices from bracket[i][j] + 1 to j
printParenthesis(bracket[i][j] + 1, j, bracket, name);

std::cout << ")";
}

// Function to find the minimum cost required to multiply the matrices
int matrixChainOrder(std::vector<int>& dims)
{
int n = dims.size() - 1; // number of matrices

// Create matrices to store the minimum cost and optimal
// parenthesized sequence order
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
std::vector<std::vector<int>> bracket(n, std::vector<int>(n, 0));

// Compute minimum cost for all chain lengths from 2 to n
for (int len = 2; len <= n; ++len)
{
for (int i = 0; i <= n - len; ++i)
{
int j = i + len - 1;
dp[i][j] = INT_MAX;

for (int k = i; k < j; ++k)
{
// Compute the cost of multiplying matrices from i to k
// and from k+1 to j, and add them to the cost of multiplying
// the resulting matrices
int cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];

if (cost < dp[i][j])
{
dp[i][j] = cost;
bracket[i][j] = k; // Store the index at which the sequence is split
}
}
}
}

// Print the optimal parenthesized sequence order
char name = 'A';
std::cout << "Optimal Parenthesized Sequence Order: ";
printParenthesis(0, n - 1, bracket, name);
std::cout << std::endl;

return dp[0][n - 1];
}

int main()
{
// Input the dimensions of the matrices
std::vector<int> dims = {10, 100, 5, 50};

// Find the minimum cost required to multiply the matrices
int minCost = matrixChainOrder(dims);

// Print the minimum cost
std::cout << "Minimum Cost: " << minCost << std::endl;

return 0;
}
```