Решения/събтаскове:

1. Малък събтаск, примерно N<=10, за вскякави експоненциални решения.

2. Всякакви кубични dp без значение по N/M.

3. NM dp. Тук има две идеи:

  1. Попълваме всяка клетка в дп-то като пробваме всеки интервал в който се съдържа
  и вземаме минмалната цена на такъв интервал + цена на левия му край.

  2. Попълваме само десните краища на интервалите, като ценан а интервала + минимума в него.

4. След това NN dp. Същото като 3.2. но си компресираме координатите леко,
така че да скипваме непопълнените клетки.

5. Тук правим леко отклонение и забравяме за dp, ами третираме интервалите като ребра,
позициите като върхове, и имаме безплатни ребра назад между съседните позиции.
Това са O(M) ребра и затова, сложността ни е M log с дийкстра.

6. Същата идея, но задни ребра слагаме само между краища на интервали. Така имаме O(N) ребра.
И сложността е N log отново с дийкстра.

Алтернативно - естественото продължение на dp-то пак имаме същата идея, но вместо линейно да търсим минимума,
използваме дърво за rmq-то. Сложността е отново N log, но няколко пъти по-бързо от 6.

RMQ-то може да е нормално такова или вариант със стак който се възползва от това че десните краища на заявките са монотонни.

Оценяване (потенциално нещо като):

1. 10 точки
2. 15 точки
3. 15 точки
4. 10 точки
5. 25 точки
6. 25 точки