По динпрогу (и по очень многим другим нужным на олимпиадах темам) безусловно стОит смотреть одну из наиболее полных, понятных и цитируемых книг по Алгоритмам -- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Издательский дом “Вильямс”, 2005.
Кроме того, смею заявить, что и по олимпиадам вообще и по динпрогу в частности вроде как неплохо в Порублёв, Ставровский, Алгоритмы и программы. Решение олимпиадных задач. Диалектика, 2007.
Что касается упомянутой задачи про овец, то у меня есть большое подозрение что там потерялась часть условия. В том виде как она есть динпрог не нужен, там всё очень даже жадно (тупо найти max_i{p_i*2^i}). А вот если добавить какие-нибудь ограничения на кол-во овец или что-то подобное, тогда и впрямь навевает на мыслм о динпроге...
__________________
Ilya Porublyov
|