Cod sursa(job #1527633)
Utilizator | Draghici Andrei andi12 | Data | 18 noiembrie 2015 15:13:30 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <cstdio>
using namespace std;
int d[501][501];
int a[501];
int main()
{
FILE *in,*out;
in=fopen("podm.in","r");
out=fopen("podm.out","w");
int n,i,min,var,j,k;
fscanf(in,"%d",&n);
for(i=1;i<=n+1;i++)
fscanf(in,"%d",&a[i]);
for(i=1;i<=n;i++)
d[i][i]=0;
for(i=n-1;i>=1;i--)
for(j=i+1;j<=n;j++)
{
min=999999;
for(k=i;k+1<=j;k++)
{
if(d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]<min)
min=d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1];
}
d[i][j]=min;
}
fprintf(out,"%d",d[1][n]);
return 0;
}