Cod sursa(job #3237055)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 4 iulie 2024 15:08:29
Problema Parantezare optima de matrici Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.51 kb

#include <fstream>
#include <vector>
using namespace std;
ifstream cin("podm.in");
ofstream cout("podm.out");
int n;
vector<long long> A;
long long dp[503][503];
int main()
{
    cin>>n;
    A.resize(n+1);
    for(int i=0;i<=n;i++)
       cin>>A[i];
    for(int i=n-1;i>=1;i--)
       for(int j=i+1;j<=n;j++)
       {
           dp[i][j]=0x3f3f3f3f;
           for(int k=i;k<j;k++)
             dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+A[i-1]*A[k]*A[j]);
       }
    cout<<dp[1][n];
    return 0;
}