ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1167. Bicolored Horses

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