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

## How to solve the problem

**Moderator:** Board moderators

### Re: How to solve the problem

I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.windows2k wrote: 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

### Re: How to solve the problem

I thoguht I have found a rough method to solve.gawry wrote:I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.windows2k wrote: 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

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