Тема: Динамика по профилю. Задача "паркет"
Может ктонибудь обьяснить решение предложеное в алгоритмах?
Re: Динамика по профилю. Задача "паркет"
http://informatics.mccme.ru/moodle/mod/ … php?id=290 - объяснения, обратите внимание на левую колонку.
http://informatics.mccme.ru/moodle/mod/ … php?id=477 - 5 задач на эту тему.
http://informatics.mccme.ru/moodle/mod/ … php?id=489 - разбор задач.
Re: Динамика по профилю. Задача "паркет"
Кстати доминошную динамику можно реализовать и за O(M*N*M^2)
Re: Динамика по профилю. Задача "паркет"
Oleg пишет:
Кстати доминошную динамику можно реализовать и за O(M*N*M^2)
А как?
Re: Динамика по профилю. Задача "паркет"
Например можно почитать тут http://forums.topcoder.com/?module=Mess … ID=1111225
Re: Динамика по профилю. Задача "паркет"
Там не про O(M*N*M^2), а про O(M*N*2^M)
Тем не менее, количество замощений доминошками прямоугольника все же можно считать за полиномиальное время)
Re: Динамика по профилю. Задача "паркет"
Упс. Конечно описался 
Re: Динамика по профилю. Задача "паркет"
На Тимусе есть такая задача
http://acm.timus.ru/problem.aspx?space=1&num=1594
Правда ее сдало всего 9 человек и я не из их числа. Интересно было бы узнать, как все-таки она делается.
В обсуждении есть формула, но в ней фигурируют синусы и косинусы, потому по ней считать нельзя.
Re: Динамика по профилю. Задача "паркет"
KADR
гугли по "ацтекскому диаманту"...
Re: Динамика по профилю. Задача "паркет"
Я находил статьи про Aztec Diamond, но связи с этой задачей я не вижу.
Re: Динамика по профилю. Задача "паркет"
Например, статья Кохася "Разбиение ацтекских диамантов и квадратов на домино". У нас правда не квадрат, но всё равно по-моему вся информация есть в этой или подобных статьях. Кстати, в ней приводится и некая формула Кастелейна, которая как раз основана на косинусах и синусах.
12 2009-10-14 01:25:42 Отредактировано winger (2009-10-14 01:26:04)
Re: Динамика по профилю. Задача "паркет"
Вообще, есть общий полиномиальный алгоритм для подсчета количества паросочетаний в планарном графе, правда к этой зададаче он не подходит (сложность порядка O(n^3)*(сложность длинного умножения n-битных чисел), где n - количество вершин в графе)
Re: Динамика по профилю. Задача "паркет"
Можно про последний поподробнее?
Re: Динамика по профилю. Задача "паркет"
Статья: http://alexandria.tue.nl/repository/fre … 597563.pdf
Собственно алгоритм:
1) ориентируем граф так, чтобы у каждой грани было нечетное число ребер, ориентированных по часовой стрелке
2) берем знаковую матрицу смежности (она будет антисимметричной)
3) считаем пфаффиан (корень из определителя, http://en.wikipedia.org/wiki/Pfaffian) этой матрицы. Он и будет количеством паросочетаний