Mai intai trebuie sa te autentifici.

Cod sursa(job #1000538)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 23 septembrie 2013 09:22:22
Problema Parantezare optima de matrici Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>
#include<algorithm>

#define NMAX 507
#define LL long long

using namespace std;

LL D[NMAX][NMAX], a[NMAX], n;
LL INF = 1 << 25;

void dinamic(){
    INF *= INF;
    for(int Lung = 2; Lung <= n; ++ Lung)
        for(int i = 1; i <= n - Lung + 1; ++ i){
            int j = i + Lung - 1;
            D[i][j] = INF;
            for(int k = i; k <= j - 1; ++ k)
                D[i][j] = min(D[i][j], D[i][k] + D[k + 1][j] + a[i - 1] * a[k] * a[j]);
        }
}

int main(){
    freopen("podm.in", "r", stdin);
    freopen("podm.out", "w", stdout);
    scanf("%lld", &n);
    for(int i = 0; i <= n; ++ i)
        scanf("%lld", &a[i]);
    dinamic();
    printf("%lld", D[1][n]);
    return 0;
}