Cod sursa(job #1620908)
Utilizator | Gagea Eusebiu-Andrei eusebiu_gagea | Data | 29 februarie 2016 13:56:15 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.79 kb |
#include <fstream>
using namespace std;
ifstream f("podm.in");
ofstream g("podm.out");
unsigned long long p[100],nr[100][100];
int n;
int main()
{
int i,j,d,km,k;
unsigned long long vm,v;
f>>n;
for(i=1; i<=n+1; i++)
f>>p[i];
for(i=1; i<n; i++)
nr[i][i+1]=p[i]*p[i+1]*p[i+2];
for(d=3; d<=n; d++)
for(i=1, j=d; j<=n; i++, j++)
{
vm=nr[i+1][j]+p[i]*p[i+1]*p[j+1];
km=i;
for(k=i+1; k<j; k++)
{
v=nr[i][k]+nr[k+1][j]+p[i]*p[k+1]*p[j+1];
if(v<vm)
{
vm=v;
km=k;
}
}
nr[i][j]=vm;
nr[j][i]=km;
}
g<<nr[1][n]<<'\n';
}