Cod sursa(job #615023)
| Utilizator | Data | 8 octombrie 2011 12:58:08 | |
|---|---|---|---|
| Problema | Parantezare optima de matrici | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.49 kb |
#include <fstream>
using namespace std;
#define dim 501
int mat[dim][dim],v[dim];
int main()
{
ifstream fin("podm.in");
ofstream fout("podm.out");
int n, i,j;
fin>>n;
for(i=1;i<=n+1;++i)
fin>>v[i];
for(i=1;i<n;++i)
mat[i][i+1]=v[i]*v[i+1]*v[i+2];
int k;
for(k=1;k<=n-2;++k)
{
j=k+2;
for(i=k;i>=1;--i)
{
mat[i][j]=min(mat[i][j-1]+v[1]*v[j]*v[j+1],mat[i+1][j]+v[1]*v[2]*v[j+1]);
}
}
fout<<mat[1][n];
return 0;
}