Cod sursa(job #3228549)
Utilizator | Alexei Niculae alexei_barosu | Data | 8 mai 2024 18:54:03 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podmn.out");
int main()
{
int n,d[505][505]= {0},v[505]= {0};
fin>>n;
for (int i=0; i<=n; i++)
{
fin>>v[i];
}
for (int i=1; i<=n; i++)
{
d[i][i]=0;
d[i][i+1]=v[i-1]*v[i]*v[i+1];
}
for (int k=2; k<=n-1; k++)
{
for (int i=1; i<=n-k; i++)
{
d[i][i+k]=1<<30;
for (int l=i+1; l<=i+k; l++)
{
d[i][i+k]=min(d[i][i+k],d[i][l-1]+d[l][i+k]+v[i-1]*v[l-1]*v[i+k]);
}
}
}
fout<<d[1][n];
return 0;
}