Cod sursa(job #2416847)
Utilizator | Stelian Chichirim stelian2000 | Data | 28 aprilie 2019 12:52:51 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <bits/stdc++.h>
using namespace std;
int v[510];
long long d[510][510];
int main()
{
freopen("podm.in","r",stdin);
freopen("podm.out","w",stdout);
int n;
scanf("%d",&n);
n++;
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int l=2;l<n;l++)
for(int i=1;i+l<=n;i++)
{
int j=i+l;
d[i][j]=1e18;
for(int k=i+1;k<j;k++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]+1LL*v[i]*v[k]*v[j]);
}
printf("%lld",d[1][n]);
return 0;
}