Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Cutting Sticks

10003.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int len, n;

int cuts[60];
int table[60][60];

int
calc(int beg, int end) {
	int i;
	int min=1000000000;

	if (beg+1==end) {
		return 0;
	}
	if (beg+2==end) {
		return cuts[end]-cuts[beg];
	}
	if (table[beg][end]) {
		return table[beg][end];
	}
	for (i=beg+1; i<end; i++) {
		int cost = calc(beg,i) + calc(i,end);
		if (cost < min) {
			min = cost;
		}
	}
	return table[beg][end] = cuts[end]-cuts[beg] + min;
}

int
main(void) {
	int i;

	while (1) {
		scanf("%d", &len);
		if (len==0) {
			break;
		}
		if (len<0 || len>=1000) abort();
		scanf("%d", &n);
		if (n>=50) abort();

		cuts[0] = 0;
		cuts[n+1] = len;
		for (i=1; i<=n; i++) {
			scanf("%d", &cuts[i]);
			if (cuts[i]<0 || cuts[i]>=len) abort();
		}
		memset(table, 0, sizeof(table));
		printf("The minimum cutting is %d.\n", calc(0, n+1));
	}
	return 0;
}