Saturday, October 6, 2007

Cutting Sticks

Yeah!!! Another one ACCEPTED...
____________________________________________________________________
Question: Cutting Sticks
____________________________________________________________________

#include "iostream.h"


int cut[52], cost[52][52];

int minCost(int start, int end) {
if(cost[start][end] != -1) return cost[start][end];
if(start + 1 == end) return cost[start][end] = 0;
int min = 65536;
for(int i = start + 1; i < end; i++) {
int c = minCost(start, i) + minCost(i, end) + (cut[end] - cut[start]);
if(c < min) min = c;
}
return cost[start][end] = min;
}

int main()
{
int l, n;
while(true) {
cin >> l;
if(l == 0) break;
cin >> n;
cut[0] = 0;
for(int i = 1; i <= n; i++) cin >> cut[i];
cut[n + 1] = l;
for(int i = 0; i <= n + 1; i++) for(int j = 0; j <= n + 1; j++) cost[i][j] = -1;
cout << "The minimum cutting is " << minCost(0, n + 1) << ".\n";
}
return 0;
}


____________________________________________________________________

No comments:

Contributors