|
|
|
|
|
|
|
Вернуться
| 1 Тер-Саркисов Богдан Олегович, 07 февраля 2025 г. 16:44:11 | |
|
Думал, что можно как-то через паросочетания решить
|
|
|
| 2 Яндулов Богдан, 07 февраля 2025 г. 14:24:19 | |
|
В каком-то смысле является: https://en.wikipedia.org/wiki/Set_cover_problem
|
|
|
| 3 Тер-Саркисов Богдан Олегович, 06 февраля 2025 г. 22:56:25 | |
|
У этой задачи стоит тема "динамическое программирование". Можно решить с помощью ДП по профилю. Но а если рассмотреть это как задачу из теории графов? Есть набор клеток и есть набор из всевозможных положений дощечек. Набор клеток это первая доля, а положения дощечек это вторая доля двудольного графа. Если дощечка покрывает клетку, то между дощечкой и клеткой есть ребро. И задача сводится к поиску наименьшего количества вершин второй доли графа, таких что все вершины первой доли связаны ребрами хотя бы с одной из выбранных вершин второй доли. Эта задача является разновидностью задачи о вершинном покрытии?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
