Pagini recente » Cod sursa (job #632262) | Borderou de evaluare (job #330070) | Cod sursa (job #1023439)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define NMAX 510
using namespace std;
unsigned long long mat[NMAX][NMAX];
unsigned long long d[NMAX+1], n;
void citire()
{
scanf("%d", &n);
for(int i = 0; i <= n; i++)
scanf("%lld", &d[i]);
}
void debug()
{
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
printf("%lld\t", mat[i][j]);
printf("\n");
}
}
void calc(int i, int j)
{
int k;
long long crt;
if(i == j)
return;
long long minim = ~(((long long)1) << 63);
for(k = i; k < j; k++)
{
crt = mat[i][k] + mat[k+1][j] + d[i]*d[k+1]*d[j+1];
if(crt < minim)
minim = crt;
}
mat[i][j] = minim;
}
void solve()
{
int i, j, k;
for(i = 1; i < n; i++)
for(j = i; j < n; j++)
calc(j-i, j);
printf("%lld", mat[0][n-1]);
}
int main()
{
freopen("podm.in", "r", stdin);
freopen("podm.out", "w", stdout);
citire();
//debug();
// printf("\n\n\n");
solve();
// printf("\n\n");
// debug();
return 0;
}