Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.
На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.
#coding=utf8
n, k = map(int, (input().split()))
stolb = list(map(int, (input().split())))
# Добавляем на 1 и последние ступени нули, т.к они без монет
stolb.insert(0, 0)
stolb.append(0)
max_step = []
# Список с макс.кол-вом монет и список с ходами
max_money = [0]
best_step = []
for i in range(1, len(stolb)):
i_prev_bs = i - 1
tmp = max_money[i_prev_bs]
for j in range(max(0, i-k), i):
if max_money[j] > tmp:
i_prev_bs = j
tmp = max_money[i_prev_bs]
max_money.append(tmp + stolb[i])
best_step.append(i_prev_bs + 1)
best_step.append(n)
best_step = set(best_step)
print(max_money[-1])
print(len(best_step) -1)
for tmp in best_step:
print(tmp, end=' ')
php solution.php
Steps: 1 2 4 6 9
Values: 10 20 30 -100 100000<?php
$k = 3;
$weight = [1 => 10, 20, -5, 30, -5, -100, -3000, -5000, 100000];
$n = count($weight);
$sum = [];
$comeFrom = [];
$sum[0] = 0;
$comeFrom[0] = 0;
for ($i = 1; $i <= $n; $i++) {
$comeFromIndex = $i - 1;
for ($j = max(0, $i - $k); $j <= ($i - 1); $j++) {
if ($sum[$j] > $sum[$comeFromIndex]) {
$comeFromIndex = $j;
}
}
$sum[$i] = $sum[$comeFromIndex] + $weight[$i];
$comeFrom[$i] = $comeFromIndex;
}
$steps = [];
while ($n) {
$steps[] = $n;
$n = $comeFrom[$n];
}
echo 'Steps: ' . implode(' ', array_reverse($steps));
echo "\n";
echo 'Values: ' . implode(' ', array_intersect_key($weight, array_combine($steps, $steps)));