Примеры
Ввод 5 1 -1 -2 3 -4 5 Вывод 3
Ввод 6 2 -1 2 -3 4 -5 6 Вывод 8
Ввод 3 0 1 2 3 Вывод 6
Для решения этой задачи можно воспользоваться динамическим программированием. Создадим массив dp размером n, где dp[i] будет хранить максимальное настроение, которое можно получить, оказавшись на i-й ступеньке.
Инициализируем dp[0] = a[0]. Затем перебираем все ступеньки от первой до последней и для каждой ступеньки пересчитываем значение dp[i] следующим образом:
dp[i] = max(dp[i], dp[j] + a[i]), где j принимает значения от 0 до i - 1 и не превышает k.
После завершения перебора всех ступенек ответом на задачу будет максимальное значение в массиве dp. Ниже представлена реализация данного алгоритма на языке Python:
n, k = map(int, input().split()) a = list(map(int, input().split()))
dp = [0] * n dp[0] = a[0]
for i in range(1, n): for j in range(max(0, i - k), i): dp[i] = max(dp[i], dp[j] + a[i])
print(dp[n - 1])
Обратите внимание: ответы, предоставляемые искусственным интеллектом, могут не всегда быть точными. Не рассчитывайте на них в критически важных областях, таких как медицина, юриспруденция, финансы или в вопросах, связанных с безопасностью. Для важных решений всегда обращайтесь к квалифицированным специалистам. Администрация сайта не несет ответственности за контент, сгенерированный автоматически.