Photolog
2010-10-12: Through the Looking-Glass
2010-10-10: My radio speaks is binary!
2010-09-16: Gigaminx: (present for my birthday)
2010-09-05: Trini on bike
2010-08-28: Valporquero
2010-08-22: My new bike!
2010-08-13: Mario and Ana's wedding
2010-08-07: Canyoning in Guara
2010-08-05: Trini and Mari in Marbella
2010-08-03: Trini and Chelo in Tabarca
Back to list of problems
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;
}