Решение оптимизации (Найдите минимальное количество времени, необходимое для того, чтобы каждый поднялся и спустился с горы)

Задача звучит так (переведено):

У подножия горы находится n (n <= 25000) человек, и все хотят подняться, затем вниз с горы. Есть 2 гида: один для того, чтобы помочь человеку подняться на гору, другой для того, чтобы помочь человеку спуститься. Человеку i требуется (i) время, чтобы подняться на эту гору, и (i) время, чтобы спуститься по ней. Однако каждый гид может помочь только 1 человеку за раз (что означает, что максимум 1 человек может подниматься, и максимум 1 человек может спускаться с горы в любой момент времени).Предположим, когда проводник «вверх» достигает вершины, он мгновенно телепортируется обратно вниз, как и проводник «вниз». Найдите как можно меньше времени, чтобы поднять и спустить всех с горы. (При необходимости люди могут собраться на вершине горы)

Вот пример ввода для задачи с моими примечаниями:

3 persons  
person 1: up=6 minutes, down=4 minutes  
person 2: up=8 minutes, down=1 minutes  
person 3: up=2 minutes, down=3 minutes

Вывод на ввод:

Минимальное количество времени - 17. Это потому, что Если первым идет человек 3, затем человек 1, а затем человек 2 (и тот же порядок используется как для подъема, так и для спуска), это дает общее время 17.

Я пробовал придумать несколько алгоритмов, но вот что у меня пока есть:

An O (n! * n) алгоритм: просто переставьте коров через все возможные перестановки, используя next_permutation

Жадный алгоритм: я отсортировал людей, уменьшив время убывания, и попытался разместить их вместе, но это не привело к правильному решению.

Другие мысли

Сейчас я обращаюсь к динамическому программированию, поскольку, согласно CLR, проблемы оптимизации обычно представляют собой жадное или динамическое программирование (эта проблема, я думаю, удовлетворяет оптимальной подструктуре).

Я заметил, что в минимальном решении «верхний» проводник не будет отдыхать, пока все не поднимутся в гору. (Так что никаких промежутков между восхождением человека 1, восхождением человека 2 и т. Д.) Может быть, проблема может быть сведена к минимизации промежутков между временами спуска?

У меня проблемы с представлением состояния для этой задачи динамического программирования (я не думаю, что она одномерная, потому что я не думаю Вы можете найти оптимальное решение для i-го человека, просто зная оптимальное решение для i-1 человека).

Кто-нибудь может помочь?