Mikail2601's blog

How to solve this problem
By Mikail2601, history, 4 years ago, In English

Hi community, recently I found this contest and i am curious to know how to solve problem BOXING BOOKS.My first tought was a dp solution

dp[i][j] = min(dp[i][j], dp[r][j — 1] + cost(i,j))

Obviusly, this solution will give TLE, My question is Can this problem be solve using Divide and Conquer? There is a simplest solution?

Thanks.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution doesn't give TLE, the time limit is 5 seconds. But if you want to do it in n * k time, it may be possible by using some convex hull trick reasoning

→ Reply