Cod sursa(job #1051895)
Utilizator | Andrei Comaneci acom | Data | 10 decembrie 2013 17:46:48 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.65 kb |
#include<cstdio>
using namespace std;
int n,v[505],a[505][505];
int main()
{
int i,j,k,l;
freopen("podm.in","r",stdin);
freopen("podm.out","w",stdout);
scanf("%d",&n);
for (i=0;i<=n;++i)
scanf("%d",&v[i]);
for (i=1,j=1,l=1;j<=n;)
{
if (i+1<j)
{
for (k=i;k<j;++k)
if (a[i][j]>a[i][k]+a[k+1][j]+v[i-1]*v[k]*v[j] || !a[i][j])
a[i][j]=a[i][k]+a[k+1][j]+v[i-1]*v[k]*v[j];
}
else if (i+1==j)
a[i][j]=v[i-1]*v[i]*v[j];
++i, ++j;
if (j>n) i=1, j=++l;
}
printf("%d\n",a[1][n]);
return 0;
}