Cod sursa(job #2696107)
Utilizator | Mustata Dumtru Sebastian seburebu111 | Data | 15 ianuarie 2021 12:41:12 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.71 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("podm.in");
ofstream out("podm.out");
long long dp[502][502];
int a[502];
int main()
{
int n;
in>>n;
for(int i=1; i<=n+1; i++)
in>>a[i];
for(int i=n-1; i>=1; i--)
{
for(int j=i+1; j<=n; j++)
{
if(i!=j)
{
dp[i][j]=1LL<<60;
for(int k=i; k<j; k++)
{
//long long prod = (long long)a[i]*a[k+1]*a[j+1];
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j] + 1LL*a[i]*a[k+1]*a[j+1]);
}
}
}
}
out<<dp[1][n];
return 0;
}