|
|
вернуться в форумSome hint 1. Инициализация Начинайте с 1 конюшни Пусть нам надо поставить туда I лошадей (I = 1..N) Коэффициент несчастья для I лошадей будет при этом равен White * Black для Horses = 0..i По итогу этого у нас будут оптимальные (потому что единственные) коэффициенты для всех лошадей в случае 1 конюшни 2. Итерации (меняем J-ую конюшню) Надо рассчитать минимальный коэффициент несчастья если в 1..J конюшни поставить I лошадей Для этого переберём все варианты, поставив в J конюшню K лошадей (K = 1..I лошади) и оптимально заполнив первые J-1 конюшни I-K лошадьми (этот коэффициент у нас уже рассчитан на предыдущем шаге итерации) Перебрав все варианты у нас получится оптимальное заполнение первых J конюшен первыми I лошадьми Переходим к J + 1 конюшне и считаем заново все варианты заполнения уже для неё |
|
|