ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1167. Bicolored Horses

Some hint
Posted by svg2003 21 Mar 2014 05:53
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 конюшне и считаем заново все варианты заполнения уже для неё