Клуб активного туризма на планете Олимпия решил предложить клиентам маршрут вдоль живописного хребта. Хребет достаточно длинный и его трудно пройти сразу, поэтому в клубе ищут самый привлекательный из маршрутов ограниченной длины. Согласно результатам социального исследования туристы любят проходить по местам, которые выше чем другие на как можно большем промежутке, благодаря более широкому обзору и эйфории от ощущения высоты.
Для упрощения задачи хребет разделили на однометровые отрезки и определили среднюю высоту над уровнем моря каждого из них. Численное значение привлекательности каждого такого отрезка хребта равно количеству последовательных отрезков слева и справа, начиная с непосредственных его соседей, которые имеют высоту строго меньшую чем он сам. Сам отрезок в эту сумму не входит. Привлекательность маршрута вычисляется как сумма привлекательностей однометровых отрезков хребта, которые в него входят. Длина маршрута должна быть не больше чем T метров. Направление маршрута значения не имеет, поскольку не меняет его привлекательности. Маршрут может начинаться с любого отрезка хребта. Маршрут не может содержать разрывов, то есть в маршрут можно включать только последовательные отрезки хребта.
Задание
Напишите программу, которая по информации о высоте над уровнем моря каждого однометрового отрезка горного хребта вычислит привлекательность наиболее привлекательного маршрута длины не больше чем T метров.
Скачать
Комментариев нет:
Отправить комментарий