Cod sursa(job #1019999)

Utilizator cristitamasTamas Cristian cristitamas Data 1 noiembrie 2013 14:47:02
Problema Parantezare optima de matrici Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#define INF 100000000000000000LL
using namespace std;

unsigned long long int A[505][505];
int d[500];
int n;

void citire(){
    scanf("%d",&n);
    for(int i=0;i<=n;++i)
        scanf("%d ",&d[i]);
}


void calculare_minim(int i,int j){
    for(int k=i;k<j;++k){
        A[i][j]=INF;
        unsigned long long int rez=A[i][k]+A[k+1][j]+d[i-1]*d[k]*d[j];
        if(rez<A[i][j]){
            A[j][i]=k;
            A[i][j]=rez;
        }
    }
}


void rezolvare(){
    for(int contor=2;contor<=n;++contor)
        for(int i=1,j=contor;j<=n;++i,++j)
            calculare_minim(i,j);
}


int main()
{
    freopen("podm.in","r",stdin);
    freopen("podm.out","w",stdout);
    citire();
    rezolvare();
    printf("%ld",A[1][n]);
    return 0;
}