Pagini recente » Borderou de evaluare (job #1686047) | Cod sursa (job #1023437)
#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("%lld", &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-1]*d[k]*d[j];
if(crt < minim && crt >= 0)
minim = crt;
}
mat[i][j] = minim;
}
void solve()
{
int i, j, k;
for(i = 1; i < n; i++)
for(j = 1; j <= n-i; j++)
calc(j, j + i);
printf("%lld", mat[0][n-1]);
}
int main()
{
freopen("podm.in", "r", stdin);
freopen("podm.out", "w", stdout);
citire();
solve();
printf("\n\n");
//debug();
return 0;
}