days дней (дни пронумерованы с нуля). В стране cities городов, и из любого можно доехать в любой другой. Начать можно в любом городе.
Таблица stay может быть составлена на больше дней, чем длится поездка, — тогда лишние строки не используются.
Каждый день путешественник выбирает одно из двух:
- остаться в текущем городе c — и получить stay[d][c] очков впечатлений, где d — номер дня;
- переехать из текущего города c в другой город t — и получить travel[c][t] очков.
Верните наибольшую сумму очков за всю поездку.cities=2, days=2, stay=[[1, 5], [4, 2]], travel=[[0, 3], [6, 0]] → 11
Начинаем в городе 1 и остаёмся там в день 0 (+5), в день 1 переезжаем в город 0 (+6). Итого 11.
cities=3, days=1, stay=[[2, 7, 1]], travel=[[0, 9, 0], [0, 0, 0], [0, 0, 0]] → 9
Один день: переезд из города 0 в город 1 даёт 9 — больше, чем остаться в любом городе.
cities=1, days=3, stay=[[4], [1], [3]], travel=[[0]] → 8
cities ≤ 200days ≤ 200days ≤ len(stay) ≤ 200, len(stay[d]) = citiestravel — квадратная матрица cities × citiesstay[d][c] ≤ 100travel[c][t] ≤ 100travel[c][c] = 0cities=2, days=2, stay=[[1, 5], [4, 2]], travel=[[0, 3], [6, 0]]
11
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 47 тестов на сервере, включая скрытые.