Cod sursa(job #1711045)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 30 mai 2016 11:05:14
Problema Parantezare optima de matrici Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

ifstream f("podm.in");
ofstream g("podm.out");

const unsigned long long mare = 0xffffffffffffffff;
unsigned long long mat[505][505], a[505];
int n, i, j, k, p;

int main(){
    f >> n;
    for (i = 0; i <= n; i++)
        f >> a[i];
    for (i = 1; i < n; i++)
        mat[i][i+1] = a[i-1] * a[i] * a[i+1];

    for (p = 2; p < n; p++)
        for (i = 1; i <= n-p; i++){
            j = i+p;
            mat[i][j] = mare;
            for (k = i; k < j; k++)
                mat[i][j] = min(mat[i][j], mat[i][k] + mat[k+1][j] + a[i-1] * a[k] * a[j]);
        }
    g << mat[1][n];
    return 0;
}