Cod sursa(job #648294)
Utilizator | Stefu Teodor Petre TeddyBoss | Data | 13 decembrie 2011 11:34:58 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include<fstream.h>
#define NM 51//2
#define INF 10000L
ifstream in("podm.in");
ofstream out("podm.out");
long long o[NM][NM],D[NM], n;
int main(){
int i,j,poz,d,k;
in>>n;
for(i=1;i<=n+1;i++)
in>>D[i];
for(d=1;d<=n-1;d++)
for(poz=1;poz<=n-d;poz++){
i=poz;
j=d+poz;
o[i][j]=INF;
for(k=i;k<j;k++){
long long min=o[i][k]+o[k+1][j]+D[i]*D[k+1]*D[j+1];
if(min<o[i][j]) o[i][j]=min;
}
}
out<<o[1][n];
return 0;
}