Алгоритм расстояния - минимум монет, необходимый для прохождения всех уровней - PullRequest
Новая
       23

Алгоритм расстояния - минимум монет, необходимый для прохождения всех уровней

0 голосов
/ 29 апреля 2018

Тор играет в игру, где есть N уровней и M типов доступного оружия. Уровни пронумерованы от 0 до N-1, а оружие пронумеровано от 0 до M-1. Он может очистить эти уровни в любом порядке. На каждом уровне требуется некоторое подмножество этого M оружия, чтобы очистить этот уровень. Если на определенном уровне ему нужно купить x нового оружия, он заплатит за него x ^ 2 монеты. Также обратите внимание, что он может нести все имеющееся у него оружие на следующий уровень. Изначально у него нет оружия. Можете ли вы найти минимальное количество монет, необходимое для прохождения всех уровней?

Формат ввода

Первая строка содержит 2 целых числа через пробел:

N = количество уровней в игре

М = количество видов оружия

N строк следуют. В i-й из этих строк содержится двоичная строка длиной M. Если j-ый символ этой строки равен 1, это означает, что нам нужно оружие типа j, чтобы очистить i-й уровень.

Ограничения

1 <= N <= 20 </p>

1 <= M <= 20 </p>

Формат вывода

Выведите единственное целое число, которое является ответом на проблему.

Образец TestCase 1

Ввод 

1 4 
0101

выход 

4

Объяснение

В этой игре только один уровень. Нам нужно 2 вида оружия - 1 и 3. Поскольку у Тора изначально нет оружия, ему придется его купить, что обойдется ему в 2 ^ 2 = 4 монеты.

Образец TestCase 2

Ввод 

3 3 
111
001
010

выход 

3

Объяснение

В этой игре 3 уровня. 0-й уровень (111) требует все 3 вида оружия. 1-й уровень (001) требует только оружие типа 2. 2-й уровень требует только оружие типа 1. Если мы очистим уровни в указанном порядке (0-1-2), общая стоимость = 3 ^ 2 + 0 ^ 2 + 0 ^ 2 = 9 монет. Если мы очистим уровни в порядке 1-2-0, это будет стоить = 1 ^ 2 + 1 ^ 2 + 1 ^ 2 = 3 монеты, что является оптимальным способом.

1 Ответ

0 голосов
/ 30 апреля 2018

Прелесть ответа Гассы отчасти заключается в том, что если можно достичь другого состояния, or используя одну из цепочек масок уровней с текущим состоянием, мы гарантируем, что достижение текущее состояние не включает посещение этого уровня (так как в противном случае эти биты уже были бы установлены). Это означает проверку перехода из одного состояния в другое путем добавления другой битовой маски, что гарантирует, что мы смотрим на порядок, в котором еще не была эта маска. Таким образом, формулировка, подобная Гассе, могла бы сработать: пусть f(st) представляет стоимость достижения состояния st, затем: 

f(st) = min(
  some known cost of f(st),
  f(prev_st) + (popcount(prev_st | level) - popcount(prev_st))^2
)
for all level and prev_st that or to st
...