1651.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define NMAX 103
#define INF 1000000000
int S,N;
int a[NMAX][NMAX][NMAX];
int m[NMAX][NMAX];
int b[NMAX];
void solve()
{
	int i,j,k;
	for(i=1;i<=N;i++)
		for(j=i+1;j<=N;j++)
			for(k=j+1;k<=N;k++)
				a[i][j][k]=b[i]*b[j]*b[k];
	for(i=1;i<=N-1;i++)
		m[i][i+2]=a[i][i+1][i+2];
	int min;
	for(i=3;i<=N-1;i++)
	{
		for(j=1;j<N;j++)
		{
			if(j+i>N)
				break;
			min=INF;
			for(k=j+1;k<j+i;k++)
			{
				if(min>a[j][k][j+i]+m[j][k]+m[k][j+i])
					min=a[j][k][j+i]+m[j][k]+m[k][j+i];
			}
			m[j][j+i]=min;
		}
	}
	printf("%d",m[1][N]);


}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d",&N);
	memset(a,0,sizeof(a));
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&b[i]);
	}
	solve();
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}