Cod sursa(job #785359)

Utilizator danalex97Dan H Alexandru danalex97 Data 8 septembrie 2012 16:39:29
Problema Parantezare optima de matrici Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
using namespace std;

typedef long long i64;

const int Maxn = 505;
const i64 oo = ( 1LL )<< 60;

i64 Best[Maxn][Maxn], A[Maxn];
int N;

ifstream F("podm.in");
ofstream G("podm.out");

#define min(a, b) ((a) < (b) ? (a) : (b))

int main(void)
{
    F>>N;
	for (int i=0;i<=N;++i)
		F>>A[i];

	for (int i=0;i<=N;++i) Best[i][i] = 0;
    for (int i=1;i<N;++i) Best[i][i + 1] = A[i - 1] * A[i] * A[i + 1];
    for (int w=2;w<N;++w)
		for (int i=1;i<=N-w;++i)
		{	int j = i + w;
			Best[i][j] = oo;
			for (int k=i;k<j;++k)
				Best[i][j] = min(Best[i][j], Best[i][k] + Best[k + 1][j] + A[i - 1] * A[k] * A[j]);
		}
	
	G<<Best[1][N]<<'\n';
}