Page **1** of **1**

### How to solve the problem

Posted: **Sun Jun 12, 2005 5:32 am**

by **windows2k**

http://acm.pku.edu.cn/JudgeOnline/show ... m_id=1738
It looks an classic DP problem, but it seems have terrible time limit.

Could someone give some hints? Thx

Posted: **Sun Jun 12, 2005 4:05 pm**

by **Per**

Looks like Huffman coding.

Posted: **Mon Jun 13, 2005 2:50 am**

by **windows2k**

Per wrote:Looks like Huffman coding.

Huffman coding can change it's sequence, but the problem doesn't.

for example, 5 3 4 5

( ( 5 ( 3 4 ) ) 5 ) it needs 36

( ( 5 3 ) ( 4 5 ) ) it needs 34

Posted: **Mon Jun 13, 2005 7:29 am**

by **Per**

Whoops, sorry. That does seem to make the problem harder.

### Re: How to solve the problem

Posted: **Thu Jun 16, 2005 6:36 pm**

by **gawry**

I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.

### Re: How to solve the problem

Posted: **Sat Jun 18, 2005 6:42 am**

by **windows2k**

gawry wrote:
I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.

I thoguht I have found a rough method to solve.

But I don't know how to reduce the time complexity from O(n^2) to O(nlogn)

Could someone give me some hints? thx

Posted: **Sun Jun 19, 2005 1:09 pm**

by **Cosmin.ro**

This seems similar to optimal matrix chain multiplication, maybe you could modify the O(n log n) algorithm for matrix chain multiplication described here

http://historical.ncstrl.org/litesite-d ... 81-875.pdf , to solve this problem.