#include <iostream>
#include <limits.h>
using namespace std;
 
int MatrixChainOrder2(int p[], int n){
	int **m = new int* [n + 1];
	int **s = new int* [n + 1];
	for(int i = 0; i < n + 1; i++){
		m[i] = new int [n];
		s[i] = new int [n];
	}
 
	for (int i = 1; i < n + 1; i++)
        m[i - 1][i - 1] = 0;
    for(int i = 0; i < n + 1; i++)
    	for(int j = 0; j < n + 1; j++){
    		m[i][j] = 0;
    		s[i][j] = 0;
    	}
 
	for(int L = 2; L < n; L++){
		for(int i = 1; i < n - L + 1; i++){
			int j = i + L - 1;
			m[i - 1][j - 1] = INT_MAX;
			for(int k = i; k < j - 1; k++){
				int q = m[i - 1][k - 1] + m[k + 1 - 1][j - 1] + p[i - 1 - 1] * p[k - 1] * p[j - 1];
				if(q < m[i - 1][j - 1]){
					m[i - 1][j - 1] = q;
					s[i - 1][j - 1] = k;
				}
			}
		}
	}
 
	// Печать матриц
	for(int i = 0; i < n + 1; i++){
		for(int j = 0; j < n + 1; j++)
			std::cout << m[i][j] << " ";
		std::cout << std::endl;
	}
	std::cout << std::endl << std::endl;
	for(int i = 0; i < n + 1; i++){
		for(int j = 0; j < n + 1; j++)
			std::cout << s[i][j] << " ";
		std::cout << std::endl;
	}
 
	return m[1][n];
}
 
int main() {
	const int n = 10;
	int p[n] = {10, 50, 30, 7, 25, 60, 15, 80, 55, 30};
	int cost = 0;
 
	std::cout << std::endl << MatrixChainOrder2(p, n - 1) << std::endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bGltaXRzLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgTWF0cml4Q2hhaW5PcmRlcjIoaW50IHBbXSwgaW50IG4pewoJaW50ICoqbSA9IG5ldyBpbnQqIFtuICsgMV07CglpbnQgKipzID0gbmV3IGludCogW24gKyAxXTsKCWZvcihpbnQgaSA9IDA7IGkgPCBuICsgMTsgaSsrKXsKCQltW2ldID0gbmV3IGludCBbbl07CgkJc1tpXSA9IG5ldyBpbnQgW25dOwoJfQoKCWZvciAoaW50IGkgPSAxOyBpIDwgbiArIDE7IGkrKykKICAgICAgICBtW2kgLSAxXVtpIC0gMV0gPSAwOwogICAgZm9yKGludCBpID0gMDsgaSA8IG4gKyAxOyBpKyspCiAgICAJZm9yKGludCBqID0gMDsgaiA8IG4gKyAxOyBqKyspewogICAgCQltW2ldW2pdID0gMDsKICAgIAkJc1tpXVtqXSA9IDA7CiAgICAJfQoKCWZvcihpbnQgTCA9IDI7IEwgPCBuOyBMKyspewoJCWZvcihpbnQgaSA9IDE7IGkgPCBuIC0gTCArIDE7IGkrKyl7CgkJCWludCBqID0gaSArIEwgLSAxOwoJCQltW2kgLSAxXVtqIC0gMV0gPSBJTlRfTUFYOwoJCQlmb3IoaW50IGsgPSBpOyBrIDwgaiAtIDE7IGsrKyl7CgkJCQlpbnQgcSA9IG1baSAtIDFdW2sgLSAxXSArIG1bayArIDEgLSAxXVtqIC0gMV0gKyBwW2kgLSAxIC0gMV0gKiBwW2sgLSAxXSAqIHBbaiAtIDFdOwoJCQkJaWYocSA8IG1baSAtIDFdW2ogLSAxXSl7CgkJCQkJbVtpIC0gMV1baiAtIDFdID0gcTsKCQkJCQlzW2kgLSAxXVtqIC0gMV0gPSBrOwoJCQkJfQoJCQl9CgkJfQoJfQoKCS8vINCf0LXRh9Cw0YLRjCDQvNCw0YLRgNC40YYKCWZvcihpbnQgaSA9IDA7IGkgPCBuICsgMTsgaSsrKXsKCQlmb3IoaW50IGogPSAwOyBqIDwgbiArIDE7IGorKykKCQkJc3RkOjpjb3V0IDw8IG1baV1bal0gPDwgIiAiOwoJCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7Cgl9CglzdGQ6OmNvdXQgPDwgc3RkOjplbmRsIDw8IHN0ZDo6ZW5kbDsKCWZvcihpbnQgaSA9IDA7IGkgPCBuICsgMTsgaSsrKXsKCQlmb3IoaW50IGogPSAwOyBqIDwgbiArIDE7IGorKykKCQkJc3RkOjpjb3V0IDw8IHNbaV1bal0gPDwgIiAiOwoJCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7Cgl9CgoJcmV0dXJuIG1bMV1bbl07Cn0KCmludCBtYWluKCkgewoJY29uc3QgaW50IG4gPSAxMDsKCWludCBwW25dID0gezEwLCA1MCwgMzAsIDcsIDI1LCA2MCwgMTUsIDgwLCA1NSwgMzB9OwoJaW50IGNvc3QgPSAwOwoJCglzdGQ6OmNvdXQgPDwgc3RkOjplbmRsIDw8IE1hdHJpeENoYWluT3JkZXIyKHAsIG4gLSAxKSA8PCBzdGQ6OmVuZGw7CglyZXR1cm4gMDsKfQ==