Задача подъема на холм, требующая программирования Dynami c

Question

Итак, в основном проблема в том, что есть серия точек холма. мы можем перемещаться только от одной точки холма к следующей более высокой точке холма.

Пожалуйста, посмотрите изображение ниже, чтобы получить представление.

On above image black points are hill tops, each hill top has some spices with some taste value. we can move from one hill top to another tasting spices in them.

Please See below image to know valid movements. green lines gives valid movements. введите описание изображения здесь

Итак, теперь нам будет дан запрос с 2 целыми числами b, c, и для каждого запроса нам нужно определить, возможно ли перемещение от точки холма b к c. если это так, то мы должны вывести общую вкусность путешествия.

Предположим, приходит запрос, в котором b = 1, c = 10.

Итак, нам нужно найти, движемся ли мы из Возможны холмы с 1 по 10, и если это так, мы должны вывести вкус путешествия. найти, возможно ли достижение от 1 до 10, и если это возможно, мы суммируем вкус.

для этой конкретной проблемы наш путь будет 1 -> 2 -> 6 -> 7- -> 9 -> 10.

Но если запрос приходит такой, что b = 1, c = 11.

, мы не можем go от 1 до 11, следовательно, нет возможен путь и ответ -1.

Но когда есть очень большие запросы, мы можем повторять l oop для каждого запроса. Я имею в виду, что мы должны предварительно обработать данные, чтобы в каждом запросе мы просто вычисляли результат за постоянное время.

Что конкретно я хочу знать?

How can i know if reaching from b to c is possible or not in constant time.

If path is possible than how to calculate the sum of path in constant time.

Answer 1

Вы можете решить эту проблему с помощью пространства O (n) и времени O (n + q), где q - количество запросов с использованием алгоритма наименьшего общего предка. Вот руководство по алгоритму топкодера , которое объясняет алгоритм.

Чтобы преобразовать проблему в эту форму, определите узел для каждого холма, и пусть родительский узел узла будет холмом, который мы можем перейти от этой точки. Введите один дополнительный узел root, который является родительским для любых холмов, у которых нет допустимого перемещения.

Затем, чтобы определить, существует ли путь от b до c, вы просто проверяете, есть ли LCA (b, c) равно c.

Вы также можете предварительно вычислить за O (n) сумму специй на пути, начинающемся в каждом узле и заканчивающемся на узле root. Чтобы вычислить сумму вдоль пути, вы просто вычитаете сумму, начинающуюся с c, из суммы, начинающейся с b.

Может показаться, что построить график вначале немного сложно, но это также может выполняется за O (n) с использованием алгоритма следующего большего элемента .