Cod sursa(job #697691)
Utilizator | FMI-Alex Dobrin Barracuda | Data | 29 februarie 2012 10:35:44 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include<fstream>
#include<limits.h>
#define inf INT_MAX
#define dim 502
using namespace std;
ifstream f("podm.in");
ofstream g("podm.out");
long long a[dim],n,i,j,D[dim][dim],l,k;
int main (){
f>>n;
for(i=1;i<=n+1;i++)
f>>a[i];
for(l=2;l<=n;l++){
for(i=1,j=l;j<=n;i++,j++){
D[i][j]=inf;
for(k=i;k<=j;k++){
if(D[i][j]>D[i][k]+D[k+1][j]+(long long)a[j+1]*a[k+1]*a[i] )
D[i][j]=D[i][k]+D[k+1][j]+(long long)a[j+1]*a[k+1]*a[i];
}
}
}
g<<D[1][n];
return 0;
}