Cod sursa(job #501963)

Utilizator vlad.maneaVlad Manea vlad.manea Data 17 noiembrie 2010 11:13:43
Problema Parantezare optima de matrici Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <cstdio>
long long col[501], opt[501][501];
int main() {
	int i, j, k, l, N;
	long long c, m;
	const long long f = 9223372036854775807LL;
	freopen("podm.in", "r", stdin);
	scanf("%d", &N);
	for (i = 0; i <= N; ++i) {
		scanf("%lld", &col[i]);
	}
	for (k = 2; k <= N; ++k) {
		for (i = 1; i + k - 1 <= N; ++i) {
			j = i + k - 1;
			m = f;
			for (l = i; l < j; ++l) {
				c = opt[i][l] + opt[l + 1][j] + col[i - 1] * col[l] * col[j];
				if (c < m) {
					m = c;
				}
			}
			opt[i][j] = m;
		}
	}
	freopen("podm.out", "w", stdout);
	printf("%lld\n", opt[1][N]);
	return 0;
}