Cod sursa(job #2937148)
Utilizator | Data | 9 noiembrie 2022 23:28:48 | |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <iostream>
#include <fstream>
#define nmax 505
using namespace std;
int n,mx,v[nmax],dp[nmax][nmax];
int main()
{
ifstream f ("podm.in");
ofstream g ("podm.out");
f>>n;
for (int i=0; i<=n; i++)
f>>v[i];
for (int d=1; d<n; d++)
{
for (int left=0; left<n-1; left++)
{
int right=left+d+1;
dp[left][right]=INT_MAX;
for (int mid=left+1; mid<right; mid++)
{
dp[left][right]=min(dp[left][right],dp[left][mid]+dp[mid][right]+v[left]*v[mid]*v[right]);
}
}
}
g<<dp[0][n];
}