| Условие задачи | | Прогресс |
|
Темы:
Динамическое программирование в играх
Вася очень хочет попасть на сборы в СУНЦ и, к счастью, живет недалеко от него. Поэтому он решил дойти до места проведения сборов пешком. Васе известен план города - какие перекрестки соединены улицами и сколько времени требуется, чтобы пройти по каждой улице. Движение по любой улице разрешено в обе стороны.
Администрация города, однако, решила устроить в этот день уборку улиц от снега. Если на какой-то из улиц происходит уборка, то движение по ней замедляется в два раза. В распоряжении города есть K снегоуборочных машин.
Вася хочет добраться до места назначения как можно быстрее, однако у главы администрации есть с Васей старые счеты, поэтому он хочет максимально замедлить его движение. В результате всякий раз, когда Вася оказывается на перекрестке, глава администрации выбирает не более K улиц, на которых будет производиться уборка, пока Вася перемещается с текущего перекрестка до следующего.
Дом Васи находится около перекрестка с номером 1, а СУНЦ - около перекрестка с номером N. Таким образом, перемещение Васи от дома до СУНЦа выглядит следующим образом. В начале глава выбирает дороги, на которых будет проводиться уборка, затем Вася выбирает улицу, по которой он пойдет от перекрестка 1 (Вася достаточно наблюдателен, чтобы заметить, на каких улицах идет уборка). Когда он доходит до конца выбранной улицы и оказывается на перекрестке, процесс повторяется: глава вновь выбирает улицы для уборки, и машины туда мгновенно перемещаются, а затем Вася - улицу, по которой идти, и т. д. Процесс продолжается, пока Вася не попадет в СУНЦ.
Ваша задача - выяснить, за какое минимально возможное время Васе удастся достичь СУНЦа при условии, что глава администрации всегда действует оптимально.
Входные данные
Первая строка содержит числа N - количество перекрестков в городе, M - количество улиц и K - количество снегоуборочных машин (1 <= N <= 100, 0 <= K <= M <= 20000). Следующие M строк содержат описания улиц в следующем формате: a и b - номера перекрестков, которые данная улица соединяет, t - время движения по данной улице (целое положительное число, не превосходящее 1000).
Выходные данные
Выведите одно число - минимальное время, за которое Вася может добраться до СУНЦа. или -1, если добраться туда невозможно.
| |
![]()
|
|
Темы:
Динамическое программирование в играх
В одном государстве имеется N городов. Некоторые города соединены дорогами, причем для любых двух городов A и B выполняется следующее свойство: существует ровно один способ попасть из города A в город B если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.
Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов A, B и C минимальное количество дорог, которое необходимо использовать, чтобы доехать от A до B, затем от B до C и затем от C до A (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).
Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.
Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).
Входные данные
В первой строке вводится число N - количество городов (3 <= N <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит Ki - количество городов, с которыми он соединен дорогами (1 <= Ki < N), а затем Ki чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.
Выходные данные
Выведите три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них
| |
![]()
|
|
Темы:
Динамическое программирование: два параметра
Динамическое программирование в играх
Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.
Входные данные
В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число K. Все числа в строке разделены пробелами.
Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000.
Выходные данные
Вывести одно число - максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.
| |
![]()
|