Cod sursa(job #377366)

Utilizator aghamatMorariu Razvan aghamat Data 24 decembrie 2009 11:42:16
Problema Parantezare optima de matrici Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#define DIM 505
#define INF 999999999
#define Min(a, b) ((a) < (b) ? (a) : (b)) 
#define int64 long long int

int64 best[DIM][DIM], d[DIM], n, i, j, k, p;

int main()
{
    freopen("podm.in","r",stdin);
    freopen("podm.out","w",stdout);
    scanf("%lli",&n);
    for ( i=0; i<=n; ++i)
        scanf("%lli",&d[i]);
    for ( i=1; i<n; ++i)  best[i][i+1]=d[i-1]*d[i]*d[i+1]; 
    for ( j=2; j<n; ++j) 
        for ( i=1; i<=n-j; ++i)
        {
            int k=i+j;
            best[i][k]=INF;
            for ( p=i; p<k; ++p)
                best[i][k] = Min(best[i][k], best[i][p]+best[p+1][k]+d[i-1]*d[p]*d[k]);
            } 
    printf("%lli",best[1][n]);
    return 0;
    }