Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Somescout, Вы писали:

S>>Условие что при d>0, N<=200 намекает на полный перебор.

К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.

К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.

Ну, если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.

Ну и, она действительно выглядит NP-полной: по условию t[i-1] < t[i], поэтому на обратном пути гарантированно не будет ожидания, а значит нужно выбрать максимальное количество цветов на прямом пути чтобы уложиться в t[N].

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Somescout, Вы писали:

S>>Условие что при d>0, N<=200 намекает на полный перебор.

К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.

К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.

Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.

Ну и, она действительно выглядит NP-полной: по условию t[i-1] < t[i], поэтому на обратном пути гарантированно не будет ожидания, а значит нужно выбрать максимальное количество цветов на прямом пути чтобы уложиться в t[N].