Cod sursa(job #2795345)
Utilizator | Data | 6 noiembrie 2021 11:34:21 | |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <iostream>
#include <fstream>
#define MAXN 503
#define INF 30000
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
long long n, a[MAXN], dp[MAXN][MAXN];
int main()
{
fin >> n;
for(int i = 0; i <= n; i++) fin >> a[i];
for(int q = 1; q < n; q++)
{
for(int i = 1; i+q <= n; i++)
{
int j = i+q;
dp[i][j] = INF;
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]);
}
}
fout << dp[1][n];
return 0;
}