Wikioi 1048 石子归并

p1048.c

/* Wikioi - Problem 1048 */
#include <stdio.h>
#include <limits.h>

int n = 0;
int M[101][101] = {{0}};
int w[101] = {0};
int S[101] = {0};

int dp(int left, int right)
{
	
	int i = 0, k = 0;
	int min = 0;
	int *ans = &(M[left][right]);
	int v0 = 0;
	
	if( left == right )
		return 0;
	
	if( *ans )
		return (*ans);
	
	min = INT_MAX;
	v0 = S[right]-S[left]+w[left];
	for(k = left;k < right;++k)
	{
		int t = dp(left,k) + dp(k+1,right) + v0;
		if( min > t )
			min = t;
	}
	
	return (*ans = min);
}

int
main(void)
{
	int i = 0;
	
	scanf("%d", &n);
	scanf("%d", w);
	S[0] = w[0];
	for(i = 1;i < n;++i)
	{
		scanf("%d", w+i);	
		S[i] = S[i-1] + w[i];
	}
	
	printf("%d\n", dp(0, n-1));
	
	return 0;
}