Cod sursa(job #431537)
Utilizator | Casu-Pop Bogdan bogdanhm999 | Data | 1 aprilie 2010 09:27:47 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <stdio.h>
#define LL long long
int main(){
freopen("podm.in","r",stdin); freopen("podm.out","w",stdout);
int n,i,j,k,a[502];
LL d[502][502],rez;
scanf("%d",&n);
for (i=0;i<=n;++i)scanf("%d",&a[i]);
for (i=n-1;i>0;--i)
for (j=i+1;j<=n;++j){
if (j-i==1)d[i][j]=a[i-1]*a[i]*a[i+1];
else
for (k=i;k<j;++k){
rez = d[i][k] + d[k+1][j] + (LL)a[i-1]*a[k]*a[j];
if (d[i][j]==0)d[i][j]=rez;
else if (rez<d[i][j])d[i][j]=rez;
}
}
printf("%lld\n",d[1][n]);
return 0;
}