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

[shm]

Игра довольно простая. Есть последовательность чисел 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. Я думаю, что ограничения, которые наложены на числа тут неспроста и это надо использовать, но идей нет. Буду рад дельным советам.

[FasterHarder]

отсортировать по убыванию ( наибыстрейшей сортировкой )
И1 1ым ходом ВСЕГДА берет сходу 2 числа ( они макс. для всей посл. )
пропускать ход ведь смысла вроде нет ( если отр. чисел нет )
И затем И1 и И2 последовательно берут по порядку числа
-------------------
2 идея: max - heap

это так, навскидку, может и не проканает ничего из этого...

[shm]

Цитата FasterHarder @ 28.03.23, 12:07

И1 1ым ходом ВСЕГДА берет сходу 2 числа ( они макс. для всей посл. )

Идея уже терпит неудачу для моего примера. Максимальные числа - 71 и 81, но если взять 71, то максимального результата не достичь.

Добавлено 28.03.23, 12:13
Более того, порядок чисел в этой игре важен. Если отсортировать массив, то будет другой результат на переборном алгоритме.

Добавлено 28.03.23, 12:13

Цитата FasterHarder @ 28.03.23, 12:07

2 идея: max - heap

А можно более подробно?

Сообщение отредактировано: shm - 28.03.23, 12:14

[FasterHarder]

A= [69 81 71 18 35 28 12 63 5 54]

after sort

A = [ 81, 71, 69, 63, ... ]
И1 = 81 + 71 - first move
И2 = 69 - first move

опровергни

зы: или сортировать НЕЛЬЗЯ и числа поступают ПО ОДНОМУ и сразу подвергаются обработке, то тогда, да, по-другому нужно

[shm]

Цитата FasterHarder @ 28.03.23, 12:17

опровергни

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

Цитата FasterHarder @ 28.03.23, 12:17

зы: или сортировать НЕЛЬЗЯ и числа поступают ПО ОДНОМУ и сразу подвергаются обработке, то тогда, да, по-другому нужно

Сортировать можно, весь список чисел известен заранее.

[FasterHarder]

Цитата shm @ 28.03.23, 12:20

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

кто тебе сказал, что И2 отдаст число 63)
вообще понятие "глупый ход" как бы не формализован

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

если И2 берет число НА РАНДОМЕ, то макс. сумма для И1 будет меняться...

[shm]

Цитата FasterHarder @ 28.03.23, 12:28

кто тебе сказал, что И2 отдаст число 63)
вообще понятие "глупый ход" как бы не формализован

И2 всегда забирает крайнее левое число на своем ходу. Куда ж формальнее?

Добавлено 28.03.23, 12:30

Цитата FasterHarder @ 28.03.23, 12:28

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

Тут такие условия. Свои условия придумывать не надо.

Сообщение отредактировано: shm - 28.03.23, 12:30

[FasterHarder]

A= [69 81 71 18 35 28 12 63 5 54]
81 71 69 63 54 35 28 12 5

вот сумма для И1, если И2 будет макс. мешать...

Добавлено 28.03.23, 12:34
почему это слева И2 должен брать - перед ним список всех чисел
И1 отдавать слева числа, а для и2 - справа ( там минимумы )

короче все

[shm]

Цитата FasterHarder @ 28.03.23, 12:31

81 71 69 63 54 35 28 12 5

= 262 < 320

Цитата FasterHarder @ 28.03.23, 12:31

вот сумма для И1, если И2 будет макс. мешать...

[Akina]

Вот вроде элементарно всё... но чем дальше читаешь пояснения, тем больше убеждаешься, что на самом деле поставленная задача очень слабо связана с тем, что написано в вопросе. Слова вроде правильные, но вот расставлены они чёрт те как...

Цитата shm @ 28.03.23, 11:50

два игрока И1 и И2, которые последовательно берут по числу

Последовательно - это как? один за другим, или строго первое из оставшихся в списке?

Цитата shm @ 28.03.23, 11:50

И2 играет всегда "глупо" - берет 1 число на своем на своем ходу.

1 - это "одно число" или "первое число из оставшихся в списке"?

Сообщение отредактировано: Akina - 28.03.23, 16:13

[shm]

Цитата Akina @ 28.03.23, 16:10

один за другим, или строго первое из оставшихся в списке?

не понял вопроса. Можно взять только самое первое число. Но И1 может не брать вообще числе или 1 раз за игру взять 2 (крайних) числа.

Цитата Akina @ 28.03.23, 16:10

1 - это "одно число" или "первое число из оставшихся в списке"?

первое в оставшемся списке

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

n = int(input(''))
v = [int(x) for x in input('').split()]
r1 = [0] * (n + 3)
r2 = [0] * (n + 3)
r1[n - 1] = v[n - 1]
r2[n - 1] = v[n - 1]
for i in reversed(range(0, n - 1)):
    r1[i] = max(v[i] + r1[i + 2], r1[i + 1], v[i] + v[i + 1] + r2[i + 3])
    r2[i] = max(v[i] + r2[i + 2], r2[i + 1])
print(r1[0])

Проходит все тесты макс. за 70мс при допустимой 1 сек. С этой задачей мне попросил помочь знакомый студент. Лично мое мнение - препод издевается.

Сообщение отредактировано: shm - 28.03.23, 16:52

[Profi]

Какая-то неполная задача.
Если во входном массиве нельзя менять порядок, то задача сводится к определению что сейчас делать И1, брать число или пропускать и брать ли два подряд и когда.
Если можно - то задача сводится к нахождению максимальной суммы и расстановки чисел в нужном порядке.
Короче - я бы потребовал уточнения ТЗ.

[shm]

Цитата Profi @ 28.03.23, 19:04

задача сводится к определению что сейчас делать И1, брать число или пропускать и брать ли два подряд и когда.

Фактически так и есть.