Какие переходы для ДП codeforcse Петя и пауки?

Question

[alex_agaphe]

Маленький Петя любит заниматься дрессировкой пауков. У Пети есть доска размера n × m, в каждой клетке которой изначально сидит паук. Через одну секунду Петя быстро выбирает для каждого паука некоторое действие, и все они покорно выполняют свои команды. Всего есть 5 различных команд: остаться на месте или переползти из своей клетки в определенную из четырех соседних по стороне (то есть по одной команде на каждое из четырех возможных направлений). Петя дает команды таким образом, чтобы ни один паук не уполз за пределы доски. Допускается, что пауки могут ползти навстречу друг другу. Все пауки переползают одновременно, в одной клетке в итоге может оказаться более одного паука. Петя хочет знать, каким может быть максимальное возможное количество свободных от пауков клеток через одну секунду.

Мое текщее решение- хранить количество нулей для масок и исключить маски с неприавльым раположением нулей

def _spiders(n, m):
    _dp=[[0 for _ in range(2**n)] for _ in range(2**n)]
    for i in range(2**n):
        for j in range(2**n):
            _max=0
            for k in range(2**n):
                if _is_possible(i<<1, j<<1, k<<1, n+2):
                    if _max<_dp[k][i]:
                        _max=_dp[k][i]
                    _dp[i][j]=_max+_count_nulls(i, n)
    _sum=0
    for ii in range(1, m):
        for dp in _dp:
            for x in dp:
                _sum+=x
    
    return _sum

Comments

[SunTechnik]

Akina, три клетки подряд.
Пауки сползлись в среднюю клетку.
Образовалось две свободные клетки. Все условия выполнены.

[SunTechnik]

В приведенном коде написано странное.
Почему три вложенных цикла, почему в е они по одной размерности, как должна работать загадочная функция: _is_possible?

Надо понять какие максимально допустимый значения m, n, что бы оценить допустим ли метод полного перебора.

По сути задача сводится:
Разместить на доске m, n минимальное количество единиц, так что бы около каждой пустой клетки была бы рядом хотя бы одна 1.

[Akina]

SunTechnik, да, читал одно, прочитал другое... бывает.

Answer 1

[Wataru]

Сначала переформулируем задачу - надо найти минимальное количество клеток с пауками в конце. Каждая клетка доски должна быть "покрыта": или быть с пауками, или быть соседней с клеткой с пауками.

У задачи много решений.
Во-первых, можно порисовать частные случаи с маленькими досками и найти формулу.
Для мелких значений там частные случаи, а для больших можно получить формулу.

Что-то вроде такого расположения работает на больших досках:

*...*...*
..*...*..

Во-вторых, можно решать через графы. Пусть каждая клетка - вершина графа. Ребра между соседними клетками. Заметим, что граф - двудольный (шахматная раскраска доски - это и есть 2 доли). Исходная задача поиска минимального количества клеток с пауками, это фактически задача поиска контролирующего множества вершин: каждая клетка должна или быть во множестве, или быть соседней с клеткой из множества. В двудольном графе эта задача равнасильна поиску максимального паросочетания. Это решение за O(n^2m^2).

Если хотите ДП, то перед переходами надо определиться с состояниями. Ясно, что будет какое-то ДП по профилю. Будем целиком покрывать сколько-то первых строк, а состояние последней строки хранить в маске. Поскольку каждая клетка может быть покрыта как снизу, так и сверху, то в состоянии надо держать состояние 2 последних строк.
Например, состоянием может быть f(k,m1,m2) - расставили пауков в клетках их первых k строк. Считаем минимальное количество пауков. Первые k-1 целиком покрыты, строка k покрыта маской m1, а строка k+1 - маской m2. База f(0,0,0) = 0, f(0, m1, m2) = infinity. Ответ будет в min_m2 (f(n, 2**m-1, m2)).

Переход снизу вверх: перебираем, куда мы ставим пауков в строке k+1. При этом важно, что бы строка k оказалось целиком покрыта. Пресчитываем маску в строке k+1, а маска в строке k+2 - это будет куда мы поставили пауков:
F(k,m1,m2) --> F(k+1, m2 | m3 | (m3 << 1) | (m3 >> 1), m3), для всех m3, таких что m3 | m = 2**m-1

Это будет решение за O(n6^m).