Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » timus 1627
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Здравствуйте!
Собственно задачу понятно как решать - с помощью матричной теоремы Кирхгофа. Но вот вроде кто то там (в обсуждении задачи) писал что есть другое решение - ДП по профилю. Интуитивно конечно ограничения наталкивают на эту мысль, но вот как с помощью него решить ее?
Ну можно попробовать хранить для каждой клеточки в столбце номер ее компоненты связности. Тогда нужно при переходе еще перебирать все возможные способы объединения компонент в одной компоненте. Главное отсекать разные недопустимые профили и компоненты нумеровать так, чтобы верхняя клетка принадлежала первой и номера шли подряд. Думаю, тогда решение успеет.
Если я правильно помню эту задачу, то именно так мы её и решали. В смысле, динамикой по профилю, где для каждой клетки на текущем уровне храним номер её компоненты связности, так, что нумерация лексикографически минимальна (чтобы одни и те же расстановки не учитывались разными нумерациями).
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » timus 1627