Оптимальный алгоритм максимизации для игры

Игра довольно простая. Есть последовательность чисел A длины N, есть два игрока И1 и И2, которые последовательно берут по числу. Игроки ходят поочередно, но И1 начинает игру всегда первым. Смысл игры - набрать максимальную сумму чисел. И1 на своем ходу может взять 1 число или пропустить ход. Также один раз за всю игру И1 может взять 2 числа. И2 играет всегда "глупо" - берет 1 число на своем на своем ходу. Смысл задачи - просчитать максимально возможный выигрыш для И1.
Пример:
A= [69 81 71 18 35 28 12 63 5 54]
Жирным выделены числа, которые забрал И1. Результат - 320.
Ограничения N <= 10⁵, 0 <= A_i <= 100

Я потратил кучу времени на эту казалось бы простую задачу. Но лучше метода ветвей и границ ничего не придумал, но он не проходит по времени для больших N. Я думаю, что ограничения, которые наложены на числа тут неспроста и это надо использовать, но идей нет. Буду рад дельным советам.

0

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

Пусть dp[i][j] - это максимальная сумма, которую может набрать И1, если осталось взять числа с индексами от i до N-1, а И1 уже взял j чисел на предыдущих ходах. Тогда, чтобы вычислить dp[i][j], нужно рассмотреть два варианта:

1. И1 пропускает ход: dp[i][j] = dp[i+1][j].
2. И1 берет одно число: dp[i][j] = dp[i+1][j+1] + A[i].
3. И1 берет два числа: dp[i][j] = dp[i+2][j+2] + A[i] + A[i+1].

Изначально, dp[N][j] = 0 для всех j, так как если не осталось чисел, то сумма равна 0. Также, dp[i][j] = -inf для всех j > N-i, так как И1 не может взять больше чисел, чем осталось.

Итоговый ответ будет равен dp[0][0].

Вот пример кода на Python:

N = int(input())
A = list(map(int, input().split()))

# Инициализация массива dp
dp = [[-float('inf')] * (N+1) for _ in range(N+1)]
for j in range(N+1):
dp[N][j] = 0
for i in range(N):
for j in range(N-i+1):
if j > 0:
dp[i][j] = max(dp[i][j], dp[i+1][j-1] + A[i])
dp[i][j] = max(dp[i][j], dp[i+1][j])
if j < N-i-1:
dp[i][j] = max(dp[i][j], dp[i+2][j+2] + A[i] + A[i+1])

print(dp[0][0])


Этот код работает за время O(N^2) и должен быть более-менее быстрым для заданных ограничений, наверное...

1

Спасибо, пошел переваривать. У меня мало опыта использования динамического программирования, но попытаюсь понять идею. Боюсь, что N² все же все равно слишком долго окажется.

Добавлено через 16 минут
Код вроде как нерабочий, но я все же попытаюсь понять идею)

0

1. Для каждой позиции, начиная с конца, посчитать максимальную сумму без использования суперхода.
s[i] = max (a[i] + s[i+2], s[i+1])

2. Для каждой позици, начиная с начала, посчитать максимальную сумму с использованием суперхода в данной позиции.
s[k] = a[k] + a[k+1] + s[k+3]
Далее аналогично пункту 1, начиная с позиции k-1.

Получаем квадратичное время.
Подозреваю, что можно справиться за линейное время с использованием двух дополнительных массивов, но доказать не могу. Так что, возможно, нельзя.

Добавлено через 1 минуту

1

Почитал про динамическое программирование - голова опухла, много всяких умных формул, а я не математик. А что в универе было уже забыл за много лет
Короче я сам дошел до решения за O(N). Вернулся к исследованию переборочного варианта (сперва я ушел не в ту сторону на метод ветвей и границ), заметил, что много повторных вычислений в узлах дерева. Решил переделать на поиск в глубину, это позволило дать возможность закэшировать результаты вычислений. Потом в процессе отладки до меня дошло, что по факту тут хвостовая рекурсия, которую можно развернуть:
Проходит все тесты макс. за 70мс при допустимой 1 сек. С этой задачей мне попросил помочь знакомый студент. Лично мое мнение - препод издевается.

1

Сообщение от shmkv Лично мое мнение - препод издевается.

Почему издевается? Отличная задача.

0

Мне кажется избыточно сложно прийти к такому решению для рядового студента.

0