Pagini recente » Cod sursa (job #1750175) | Cod sursa (job #2775426) | Cod sursa (job #1042535) | Cod sursa (job #1027494) | Cod sursa (job #532722)
Cod sursa(job #532722)
#include <cstdio>
using namespace std;
long long d[510];
long long n;
void citire()
{
scanf("%d",&n);
for(long long i=0;i<n+1;i++)
scanf("%d",&d[i]);
}
long long x[1000][1000];
void solve()
{
long long k;
for(long long nrp=1;nrp<n;nrp++)
for (long long i=1;i<=n-nrp;i++)
{
long long min=x[i][i]+x[i+1][i+nrp]+d[i-1]*d[i]*d[i+nrp];
long long kk=0;
for (long long k=i;k<i+nrp;k++)
{ long long z=0;
z=x[i][k]+x[k+1][i+nrp]+d[i-1]*d[k]*d[i+nrp];
if(min>z)
{min=z;
kk=k;
}
}
x[i][i+nrp]=min;
x[i+nrp][i]=kk;
}
}
/*void recursiv(long long i, long long j)
{
if(i==j)
{
printf("A%d",i);
return;
}
printf("(");
recursiv(i,x[j][i]);
printf(" ");
recursiv(x[j][i]+1,j);
printf(")");
}
*/
int main()
{
freopen("podm.in","r",stdin);
freopen("podm.out","w",stdout);
citire();
solve();
//recursiv(1,4);
printf("%lld",x[1][n]);
return 0;
}