Тема: Eating Together
http://acm.pku.edu.cn/JudgeOnline/problem?id=3670
Народ, как сделать такую задачу? Тут какая-то динамика или брут-форс ?
Спасибо!
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Eating Together
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
http://acm.pku.edu.cn/JudgeOnline/problem?id=3670
Народ, как сделать такую задачу? Тут какая-то динамика или брут-форс ?
Спасибо!
Ну тут надо перебрать 2 вида конечного распределения (111222333 и 333222111). Например, пробуем сделать первый. Сделаем динамику по номеру коровы и типу последней коровы. Тогда мы смотрим, надо ли переназначать данной корове номер, а потом выбираем, как выгоднее: когда эта корова начинает новую группу(т.е. предыдущая из другой группы) или же она продолжает существующую группу(предыдущая из этой же группы).
Спасибо большое ) Получил АС (O(N*3*3)).
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Eating Together