Cod sursa(job #3225893)
Utilizator | Besu-Roca Andrei andreiqwer | Data | 19 aprilie 2024 11:58:32 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <fstream>
#include <climits>
using namespace std;
ifstream cin("podm.in");
ofstream cout("podm.out");
long long m[502][502];
long long d[502];
int main()
{
int n;
cin>>n;
for(int i=0; i<=n; i++)
cin>>d[i];
for(int i=1; i<=n; i++)
m[i][i]=0;
for(int i=1; i<=n-1; i++)
m[i][i+1]=d[i-1]*d[i]*d[i+1];
for(int w=2; w<=n-1; w++)
for(int i=1; i<=n-w; i++)
{
int j=i+w;
m[i][j]=INT_MAX;
for(int k=i; k<=j-1; k++)
m[i][j]=min(m[i][j], m[i][k]+m[k+1][j]+d[i-1]*d[k]*d[j]);
}
cout<<m[1][n];
}