Точечная игра и динамическое программирование

Пытаюсь решить вариант точечной игры с динамическим программированием.

В обычной игре с точками используется линия из точек. Каждый игрок берет одну или две точки на соответствующем конце линии, и тот, у кого не осталось точек, побеждает.

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

У меня проблемы с осознанием этого и попыткой написать повторение решения. Любая помощь приветствуется, спасибо!


recurrence algorithm dynamic-programming
person Albert Diego    schedule 04.05.2010    source источник
comment
Какова цель вашей версии игры? Чтобы максимально увеличить количество набранных очков? Или, может быть, чтобы увеличить разницу между вашими очками и очками оппонента?   -  person Gabe    schedule 04.05.2010
comment
@Gabe: поскольку, насколько я понимаю, общее количество баллов фиксировано, эти два варианта, о которых вы говорите, абсолютно одинаковы.   -  person o0'.    schedule 05.05.2010

Ответы (1)


arrow_upward
4
arrow_downward

Взгляните на этот сайт: http://people.csail.mit.edu/bdean/6.046/dp/, особенно проблема № 10:

Оптимальная стратегия игры. Рассмотрим строку из n монет значений v (1) ... v (n), где n четное. Мы играем против соперника поочередно. На каждом ходу игрок выбирает первую или последнюю монету из ряда, навсегда удаляет ее из ряда и получает значение монеты. Определите максимально возможную сумму денег, которую мы определенно можем выиграть, если сделаем ход первым.

Это именно то, что вам нужно, если я правильно читаю ваш пост. Решение довольно простое, и, на мой взгляд, оно очень хорошо объяснено.

person IVlad    schedule 04.05.2010
comment
Боже мой, этот сайт отличный! Я готовлюсь к соревнованиям по программированию, но я новичок и пытаюсь овладеть всеми техниками (Backtracking, Graph алгоритмы, ...), я изучаю динамическое программирование, и этот сайт мне очень поможет! У меня проблемы с рекуррентными отношениями (я могу понять ответы, но мне очень сложно разработать их в одиночку). Вы знаете какой-нибудь подобный ресурс для них? - person Alessandro Stamatto; 03.04.2011
comment
@Alessandro Stamatto - есть очень хорошее руководство по DP по топкодеру: topcoder.com/tc ? d1 = tutorials & d2 = dynProg & module = Static - а также запись в Википедии о динамическом программировании, которую вы, наверное, видели. Других я не знаю. На большинстве страниц говорится об одной или двух конкретных проблемах, поэтому, если вы на чем-то застряли, вам следует просто поискать эту проблему. Со временем вы научитесь этому. - person IVlad; 03.04.2011