SPOJ.com - Problem OPTCUT

OPTCUT - Chặt cây

no tags

You have to cut a piece of wood into n smaller pieces, each piece is of length a_i. The pieces must be cut in order exactly a₁, a₂, ..., a_n from left to right.

At each step, you may cut a piece into two smaller pieces. The cost for that cut is the length of the piece before cut.

Different cut order will result in different costs.

Find the minimum cost to cut the initial piece into n given smaller pieces.

Submit solution!

hide comments



	Simes: 2021-05-20 20:56:14 The order of the final sizes of the pieces of wood cannot vary, but the order of the cuts that produces those pieces can vary. 20 -> 3 + 17 -> 3 + 5 + 12 -> 3 + 5 + 2 + 10, for a cost of 20 + 17 + 12 = 49 20 -> 10 + 10 -> 8 + 2 + 10 -> 3 + 5 + 2 + 10, for a cost of 20 + 10 + 8 = 38 20 -> 10 + 10 -> 3 + 7 + 10 -> 3 + 5 + 2 + 10, for a cost of 20 + 10 + 7 = 37 Last edit: 2021-07-03 22:54:08
	nadstratosfer: 2021-05-20 11:39:47 I don't understand. The vietnamese statement translates: Different cutting orders will result in different total costs when cutting the log into the required n segments. (example of two different cutting orders) Find the way to chop with the lowest total cost. What can the cost depend on if the order does not vary?
	[Rampage] Blue.Mary: 2021-05-19 17:06:41 @nadstratosfer: The order can't be changed. So 10 -> 5 + (5) is invalid.
	nadstratosfer: 2021-05-19 15:30:27 (20) -> 10 + (10) -> 5 + (5) -> 3+2, total cost = 35. Why does the sample show 37?

Submit solution!

Added by:	Jimmy
Date:	2009-03-03
Time limit:	0.200s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO PERL6