README

Huffman Tree Implementation of The Rod Cutting Problem
======

Operations Research - CAS 6O03 - McMaster University

--------------------
--------------------
THE QUESTION:

Your boss asks you to cut a wood stick into pieces. The stick-cutting company, 
Machinery Asynchronous Cutting Inc. (MAC), charges money according to the length 
of the stick being cut. Different selections in the order of cutting can led to 
different prices. For example, consider a stick of length 10 meters that has to 
be cut at 2, 4 and 7 meters from one end. There are several choices. One can be 
cutting first at 2, then at 4, then at 7. This leads to a price of 10+8+6 = 24 
because the first stick was of 10 meters, the resulting of 8 and the last one of 
6. Another choice could be cutting at 4, then at 2, then at 7. This would lead 
to a price of 10+4+6=20, which is a better price.

Let n be the number of cutting points of a stick, you are asked to write an 
O(n^3) algorithm to find out the minimum cost for cutting a given stick.
--------------------
--------------------
INPUT:

The first line of each test case will contain a positive number l that 
represents the length of the stick to be cut. You can assume l < 1000. The next 
line will contain the number n (n < 50) of cuts to be made.

The next line consists of n positive numbers ci (0 < ci < l) representing the 
places where the cuts have to be done, given in strictly increasing order. 
e.g.:
	100
	3
	25 50 75
--------------------
--------------------
OUTPUT:

You have to print the cost of the optimal solution of the cutting problem, that 
is the minimum cost of cutting the given stick. 
e.g., the output for the above input should be:
	200

======
Completed by Michael Liut, M. Eng, McMaster University
======