Задание 3 Параграф 11 ГДЗ Босова 11 класс (Информатика)

1. Бобёр Билли любит жёлуди. Он хочет поплыть по течению и собрать все жёлуди на островах, мимо которых будет проплывать. Увы, течение реки настолько сильное, что он может плыть только вниз по течению. Какое максимальное количество желудей он сможет собрать? Решите эту задачу, воспользовавшись методом динамического программирования.

Решим задачу методом динамического программирования. Для каждого острова будем хранить:

• k — количество желудей на острове;
• max — максимальное число желудей, которое можно собрать, доплыв до этого острова.

Тогда для каждого следующего острова выбираем наибольшее значение max среди всех островов, из которых в него можно попасть, и прибавляем количество желудей на текущем острове.

На последнем острове получаем наибольшее значение 18, значит именно столько желудей сможет собрать Бобёр Билли.

Ответ: 18 желудей.