Pagini recente » Cod sursa (job #1226542) | Cod sursa (job #54111) | Cod sursa (job #485625) | Cod sursa (job #854935) | Cod sursa (job #787332)
Cod sursa(job #787332)
#include <cstdio>
#define mare 5000005
#include <algorithm>
using namespace std;
#define BM 505
long long m[BM][BM],n,s[BM];
long long memo(int i,int j){
if(m[i][j]==0){
if(i==j-2)return s[i]*s[j]*s[i+1];
if(i>=j-1)return 0;
m[i][j]=mare;
for(int k=i+1;k<j;++k){
m[i][j]=min(m[i][j],memo(i,k)+memo(k,j)+(s[i]*s[j]*s[k]));
}
}
return m[i][j];
}
int main () {
int i;
freopen("podm.in","r",stdin);
freopen("podm.out","w",stdout);
scanf("%lld",&n);
for(i=1;i<=n+1;++i)scanf("%lld",&s[i]);
printf("%lld",memo(1,n+1));
}