Cod sursa(job #2297594)
| Utilizator | Data | 6 decembrie 2018 09:06:16 | |
|---|---|---|---|
| Problema | Parantezare optima de matrici | Scor | 70 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.59 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
int n,i,j,k,w,d[10001],m[10001][10001];
int main()
{
fin>>n;
for(i=0;i<=n;++i)
fin>>d[i];
for(i=1;i<=n;++i)
m[i][i]=0;
for(i=1;i<=n-1;++i)
m[i][i + 1] = d[i - 1] * d[i] * d[i + 1];
for(w=2;w<=n-1;++w)
for(i=1;i<=n-w;++i){
int j = i + w;
m[i][j] = 1000000000;
for(k=i;k<=j-1;++k)
m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + d[i - 1] * d[k] * d[j]);
}
fout<<m[1][n];
return 0;
}
