Блог пользователя faiyaz26

UVA 12440 Solution Idea ?
Автор faiyaz26, 10 лет назад, По-английски

I am stuck with this problem for more than 2 years. :(

Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3871

Lightoj categorized this problem under DP and Segment tree. But I have no idea how to plug this two topic in the solution. Can anyone provide me the solution in descriptive way? :)

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I found this : http://morris821028.github.io/2014/12/09/uva-12440/ Using google translate i think you can understand most of it. It's a worst-case O(n^2) solution but fast enough to get AC. Then i changed the code to make it O(nlogn) using multiset. http://paste.ofcode.org/HL4mwrQXh8Xk8jZDFNGv3r

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

It has been discussed in a previous blog

http://codeforces.net/blog/entry/12393

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain in this solution how do we use segment tree to get min of S(k) + H(k + 1, n)?

    It seems like it's similar to 2D Segment Tree because query has 3 parameters not 2.

    Is there a way to do it in O(logn)?

    → Ответить