"Worse-to-best option", a different way to think about Slope Trick

Правка en1, от gmyu.michael, 2021-06-12 21:26:57

Background

While I was learning the "Slope Trick", I could understand the examples but had a hard time solving related problems by myself. Maybe my thinking process is just different. Along the way, I come up with a different way to think about this algorithm (and come to almost the same code.) Here I would like to share how I think about it, which I call "Worse-to-best option", inspired by the "Buy Low Sell High" problem that I'll explain below.

The Slope Trick is first explained by zscoder in this tutorial, and then further explained by Kurino in this blog. I learned from Benq USACO Guide here.

"Worse-to-best option"

The help

Теги slope trick

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский gmyu.michael 2021-06-13 06:29:44 4 Tiny change: ' [user:Kurino,2021-06-1' -> ' [user:Kuroni,2021-06-1'
en12 Английский gmyu.michael 2021-06-13 03:08:38 6 (published)
en11 Английский gmyu.michael 2021-06-13 03:06:27 447
en10 Английский gmyu.michael 2021-06-13 02:51:52 293
en9 Английский gmyu.michael 2021-06-13 02:48:33 3404
en8 Английский gmyu.michael 2021-06-13 02:40:32 2414
en7 Английский gmyu.michael 2021-06-13 02:38:30 2172
en6 Английский gmyu.michael 2021-06-12 22:43:08 20
en5 Английский gmyu.michael 2021-06-12 22:41:08 2736
en4 Английский gmyu.michael 2021-06-12 22:33:22 1077
en3 Английский gmyu.michael 2021-06-12 22:19:44 118
en2 Английский gmyu.michael 2021-06-12 22:14:36 2673 Tiny change: 'queue pq\n`pq.push(price);`\n' -> 'queue pq\n~~~~\n pq.push(price);\n~~~~\n'
en1 Английский gmyu.michael 2021-06-12 21:26:57 898 Initial revision (saved to drafts)