Cod sursa(job #648310)

Utilizator nnookiaPurcelea Iulian Valentin nnookia Data 13 decembrie 2011 11:40:14
Problema Parantezare optima de matrici Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
#include<fstream.h>
#define NM 64
#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;d++)
	for(poz=1;poz<=n-d;poz++){
		i=poz;
		j=d+poz;
		O[i][j]=INF;
		for(k=1;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;
      }