pku1651.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 49 行

#include <stdio.h>
#include <string.h>
#define SIZE 110
#define INF 100000000
int A[SIZE][SIZE];
int v[SIZE];
int N;

void outA()
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j <= N - i; j++)
			printf("%d\t", A[i][j]);
		printf("\n");
	}
}

void Solve()
{
	int i, j, k, min, tmp;
	for (i = 0; i < N; i++)
		scanf("%d", &v[i]);
	memset(A, 0, sizeof(A));
	N--;
	for (i = 1; i < N; i++)
	{
		for (j = 0; j < N - i; j++)
		{
			min = INF;
			for (k = 0; k < i; k++)
			{
				tmp = A[k][j] + A[i - k - 1][j + k + 1] + v[j] * v[j + i + 1] * v[j + k + 1];
				if (tmp < min)
					min = tmp;
			}
			A[i][j] = min;
		}
	}
	printf("%d\n", A[N - 1][0]);
}

int main()
{
	while (EOF != scanf("%d", &N) && N)
		Solve();
	return 0;
}