Cod sursa(job #2412108)
Utilizator | Ionita Dragos dragos.ionita2303 | Data | 21 aprilie 2019 17:34:31 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <iostream>
#include <cstdio>
using namespace std;
int DP[505][505];
int main()
{
freopen("podm.in", "r", stdin);
freopen("podm.out", "w", stdout);
int n, v[505];
scanf("%d", &n);
for (int i = 0; i <= n; i++) {
scanf("%d", &v[i]);
}
for (int i = 2; i <= n; i++) {
for (int x = 1, y = i; y <= n; x++, y++) {
DP[x][y] = (1 << 31) - 1;
for (int k = x; k < y; k++) {
DP[x][y] = min(DP[x][y], DP[x][k] + DP[k + 1][y] + v[x - 1] * v[k] * v[y]);
}
}
}
printf("%d", DP[1][n]);
return 0;
}