Cod sursa(job #1771695)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 5 octombrie 2016 21:34:43
Problema Parantezare optima de matrici Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <algorithm>
const int NMAX = 500;
using namespace std;
int d[NMAX+5];
long long dp[NMAX+5][NMAX+5];
int main(){
    freopen ( "podm.in", "r", stdin );
    freopen ( "podm.out", "w", stdout );
    int n, i, j, k;
    scanf ( "%d", &n );
    for ( i = 0 ; i <= n ; ++ i )
        scanf ( "%d", &d[i] );
    for ( i = 2 ; i <= n ; ++ i )
        for ( j = i - 2; j >= 0 ; -- j )
            dp[j][i] = 100000000000000000LL;
    for ( i = 1 ; i <= n ; ++ i )
        for ( j = i - 1 ; j >= 0 ; -- j )
            for ( k = j + 1 ; k < i ; ++ k )
                dp[j][i] = min ( dp[j][i], 1LL * d[i] * d[j] * d[k] + dp[j][k] + dp[k][i]);
    printf ( "%lld", dp[0][n] );
    return 0;
}