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

Автор nhphuc, история, 8 месяцев назад, По-английски

Link to problem.

Summary: Given $$$n$$$ segments, $$$i$$$-th segment is $$$(l_i,\ r_i)$$$. In one operation you can choose any $$$i$$$-th segment and increment or decrement both $$$l_i$$$ and $$$r_i$$$ by $$$1$$$. Find the minimum number of operations required to make each segment $$$i$$$ $$$(1 \lt i\leq n)$$$ intersect with segment $$$i - 1$$$.

I know how the dynamic programming works for this problem, and that it needs a slope-trick optimization, but I don't know how the two ideas work together (I have an AC submission but I don't actually understand how it works or the idea behind it). Please help me. Thanks for your attention — have a good day!

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

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Slope trick is just optimization of dynamic programming in case when function is convex and linear. I think if you view the problem from this point, it is apparent how the ideas work together?