Еще одна задача , Помогите решить задачу

Помогите решить задачу.
Надо только идея решения без исходников.
Условие:

Сообщение отредактировано: Krishkinn - 25.12.03, 10:08

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

чего тут переберать, если нам в условии сказано

След. в анализе нам придется написать функцию, которая делает выбор аппонента. Этой же функцией можно делать и свой ход.
А при всем богатстве выбора особой альтернативы у нас нет:

пример тот что выше:
6
4
7
2
9
5
2

либо 6 либо 2. Если 6 то противнику оставляем 4 и 2, Если 2 то оставляем 6 и 5.
Разница в первом варианте 6-2=4 во втором 2-5=-3 выбираем 6.

получили
(6:0)
4
7
2
9
5
2
либо ( 4 ? 7 : 2 ), ( 2 ? 4 : 5 )

4-7=-3, 2-5=-3, берем скажем первое 4

и т.д.

Чего-чего... Просто когда на очередном шаге етого самого динамического программирования получается _много_ одинаковых по стоимости (оптимальных) вариантов, в следующем шаге приходится просматривать их _все_, чтобы найти в конце концов оптимальное решение. Так уж оно устроено

А вообще, ПЕРВОЕ, что нужно сделать после получения более-менее работоспособного решения, ето проверить, как оно работает на всяких вырожденных и екстремальных входных данных, допустимых по условию задачи. Я как составитель нескольких олимпиадных задач (да и все мне известные составители тоже ) _всегда_ делал такие тесты.

Цитата

Visitor, 29.12.03, 09:33
Просто когда на очередном шаге етого самого динамического программирования получается _много_ одинаковых по стоимости (оптимальных) вариантов, в следующем шаге приходится просматривать их _все_, чтобы найти в конце концов оптимальное решение.

Тобишь что бы удостовериться, что на втором ходу я сделал правильный выбор, тобишь
взял 4, мне нужно перерыть всю! последовательность до конца, причем на каждой такой развилке удваивать кол-во перебора оставшихся чисел.

При написании ответа у меня в голове бродили мысли что может быть такая вырожденная последовательность, например для таких, выше, данных неполучилось собрать наименьшую сумму если таким подходом выбирать число дающее минимальное приращение суммы. Хотя я не уверен что вообще возможно первому игроку собрать наименьшую сумму. Во всяком случае этот алгоритм можно назвать эвристическим, а не переборным. И он точно не подвиснет на 200 единицах Потому что не имеет рекурсии.

Цитата

Visitor, 29.12.03, 09:33
Я как составитель нескольких олимпиадных задач

А вот это интересно хотел бы почитать условие, надеюсь это не N-мерные кубы ?

Не надо перерывать всю... Я ж говорю -- динамическое программирование. Если ты знаешь свои и противника оптимальные ходы и ожидаемый результат на (всех) подпоследовательностях длины 5, ты достаточно просто определишь их для подпоследовательностей длины 6...

ВТОРЫЕ почти правильные сабмиты решений вылетали обычно из-за того, что разрядности используемых промежуточных переменных не хватало для хранения промежуточных результатов. Хотя здесь, вроде бы, ето составитель предусмотрел, и такого еффекта быть не должно... Мы своих не жалели

Задачи... Вот, оказывается, в инете отчет разместили по одному из мероприятий
http://rtf.ustu.ru/OL_HTM/Olymp.htm

Сообщение отредактировано: Visitor - 29.12.03, 08:21

Игра имеет всего N^2 состояний.
Строим таблицу и заполняем от конечных к начальным.