Wikioi 1154 能量项链

p1154.c

/* Wikioi - Problem 1154. by Abreto. */
#include <stdio.h>
#define POSITION(i)	( (i) % N )

int N = 0;
int mark[201] = {0};

int M[201][201] = {{0}};
int
dp(int h, int t)
{
	int *ans = &(M[h][t]);
	int k = 0;
	int max = 0;
	
	if( h == t )
		return 0;
	
	if( *ans )
		return (*ans);
	
	max = 0;
	for(k = h;k < t;++k)
	{
		int tmp = dp(h,k) + dp(k+1,t) + mark[POSITION(h)] * mark[POSITION(k+1)] * mark[POSITION(t+1)];
		if( max < tmp )
			max = tmp;
	}
	
	return (*ans = max);
}

int
main(void)
{
	int i = 0;
	int max = 0;
	
	scanf("%d", &N);
	for(i = 0;i < N;++i)
		scanf("%d", mark+i);
	
	max = 0;
	for(i = 0;i < N;++i)
	{
		int t = dp(i, i+N-1);
		if( max < t )
			max = t;
	}
	
	printf("%d\n", max);
	return 0;
}