Pagini recente » Borderou de evaluare (job #601654) | Borderou de evaluare (job #1065069) | Borderou de evaluare (job #2149385) | Borderou de evaluare (job #517233) | Cod sursa (job #1383711)
#include <iostream>
#include <fstream>
#include <limits>
using namespace std;
const int MAXN = 505;
int matrix_chain_cost(int n, long long d[]) {
long long m[MAXN][MAXN];
for (int i = 1; i <= n; i++)
m[i][i] = 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] = numeric_limits<int>::max();
for (int k = i; k <= j - 1; k++) {
int q = m[i][k] + m[k + 1][j] + d[i - 1] * d[k] * d[j];
if (q < m[i][j]) {
m[i][j] = q;
}
}
}
}
return m[1][n];
}
int main() {
int n;
long long d[MAXN];
freopen("podm.in", "r", stdin);
freopen("podm.out", "w", stdout);
cin >> n;
for (int i = 0; i <= n; i++)
cin >> d[i];
cout << matrix_chain_cost(n, d);
return 0;
}