Pagini recente » Cod sursa (job #1017424) | Cod sursa (job #1017377)
#include <fstream>
#include <algorithm>
#define minim(a, b) ((a)<(b)?(a):(b))
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
long long D[505], DP[505][505], INF = 1 << 25;
int N;
void read()
{
fin>>N;
for(int i=0; i<=N; i++)
fin>>D[i];
}
void dynamics()
{
int i, j, k, diff;
for (i = 1 ;i < N; ++i)
DP[i][i+1] = D[i-1]*D[i]*D[i+1];
for (diff = 2; diff<=N-1; ++diff)
for (i=1; i<=N-diff; ++i)
{
j = i + diff ;
DP[i][j]=INF;
for (k = i; k< j; ++k)
DP[i][j] = minim(DP[i][j], DP[i][k] + DP[k+1][j] + D[i-1] * D[k] * D[j]);
}
}
void Print()
{
fout<<DP[1][N];
}
int main()
{
read();
dynamics();
Print();
return 0;
}