Cod sursa(job #2942851)

Utilizator alexandrubilaBila Alexandru-Mihai alexandrubila Data 20 noiembrie 2022 10:56:50
Problema Parantezare optima de matrici Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int n;
int dp[501][501];
int c[501];

int main()
{
    int n;
    f >> n;
    for(int i = 0 ; i <= n ; i++)
        f >> c[i];
    ///for (int i = 1 ; i <= n ; i++)
    ///dp[i][i] = 0; ///inmultirea de la matricea i la matricea i impune 0 operatii
    for(int lung = 2 ; lung <= n ; lung++)  ///ave, j - lung + 1 matrice de inmultit
        for(int i = 1, j = lung; j <= n ; i++, j++)
        {
            dp[i][j] = 1e18;
            for(int k = i ; k < j ; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + c[i - 1] * c[k] * c[j]);
        }

    g << dp[1][n] << '\n';

    return 0;
}