n堆石子(n<= 100)排成一行,現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù)。記為該次合并的成本。求最小成本。
第1行為1個整數(shù)n,表示石子的堆數(shù)。
第2行為n個整數(shù),表示n堆石子的各堆的數(shù)量。
第1行為一個整數(shù)m,表示最小成本。
第2行表示合并方案,用(x,y)表示二堆石子的合并方案。
例如,輸入
3
5 7 4
則應(yīng)該輸出
25
(5,(7,4))
如果輸入
8
4 1 3 2 5 1 2 3
則應(yīng)輸出
61
((4,((1,3),2)),(5,((1,2),3)))
3 5 7 4
27 (5,(7,4))
第1題簡單,一維線性動態(tài)規(guī)劃,第2題中等,2維,第3題最難,4維
先練著,以后釘釘講解