Řezání trámů

Máme dlouhý dřevěný trám, který bychom chtěli nařezat na několik menších. Konkrétně návod z Ikey požaduje trámy o délkách a₁, …, a_n cm a my máme k dispozici trám dlouhý a₁ + … + a_n cm a ochotného souseda s pilou. S jeho pomocí si vždy můžeme vybrat nějaký trám a rozříznout ho v libovolném místě na dva menší. Nic ale není zadarmo – soused si za jedno řezání účtuje cenu přímo úměrnou vynaložené námaze (kdo by byl řekl, že trámy jsou celkem těžké) – za rozříznutí trámu délky x cm zaplatíme x korun.

Zajímá nás, kolik celkově budeme muset nejméně zaplatit, abychom dostali sadu trámů požadovaných délek. Na způsobu řezání nezáleží, důležité je jen, abychom na konci měli správně dlouhé trámy.

Příklad: Chceme-li z trámu dlouhého 100 cm udělat trámy o délkách 20, 30 a 50 cm, vyplatí se ho nejprve rozříznout vejpůl, a pak jeden 50cm trám rozříznout na 20 + 30 cm. Za první řezání zaplatíme 100 korun, za druhé 50, celkem tedy 150. Kdybychom naopak nejprve trám rozřízli na kusy dlouhé 20 + 80 cm a poté delší trám rozřízli na kusy dlouhé 50 + 30cm, zaplatíme dohromady 180 kroun.

Pozor na to, že nezáleží na pořadí délek na vstupu, tedy vstup 20, 30, 50 je stejný jako vstup 20, 50, 30. (Můžete si například představit, že vstup nedostanete jako seznam, ale jako (multi)množinu.)

Nápověda: Tato úloha může svádět k různým na první pohled rozumně vypadajícím řešením, která ale ve skutečnosti ne vždy vydají optimální výsledek. Proto si svoje řešení pokoušejte dokázat/vyvrátit ještě pečlivěji než obvykle. Za hezký důkaz správnosti můžete dostat až 2 body navíc.