nhphuc's blog

By nhphuc, history, 8 months ago, In English

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!

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

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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?