Cod sursa(job #2493261)
Utilizator | Data | 16 noiembrie 2019 11:08:02 | |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
long long dp[505][505], d[505];
int main()
{
freopen("podm.in", "r", stdin);
//freopen("podm.out", "w", stdout);
scanf("%d", &n);
for(int i=0; i<=n; i++)
{
scanf("%lld", &d[i]);
}
for(int dif=1; dif<n; dif++)
{
for(int i=1; i<=n; i++)
{
long long vmin=999999999;
int j=i+dif;
for(int k=i; k<=j-1; k++)
{
vmin=min(vmin, dp[i][k]+dp[k+1][j]+d[i-1]*d[k]*d[j]);
}
dp[i][j]=vmin;
}
}
printf("%lld", dp[1][n]);
return 0;
}