Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.239.87.20] |
|
Сообщ.
#1
,
|
|||
|
Помогите решить задачу. Надо только идея решения без исходников. Условие:
|
Сообщ.
#2
,
|
|
|
А тут особо сложного ничего нет -- динамическое программирование. Подпоследовательности рассматривать в обратном порядке, от последнего оставшегося на доске числа. Первые сабмиты решений обычно заваливались на последовательности из 200 единиц, хде перебирать не надо, но получался очень большой перебор. Вторые -- на последовательности 200 раз по 200
|
Сообщ.
#3
,
|
|||
|
чего тут переберать, если нам в условии сказано
След. в анализе нам придется написать функцию, которая делает выбор аппонента. Этой же функцией можно делать и свой ход. А при всем богатстве выбора особой альтернативы у нас нет: пример тот что выше: 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 и т.д. |
Сообщ.
#4
,
|
|
|
Чего-чего... Просто когда на очередном шаге етого самого динамического программирования получается _много_ одинаковых по стоимости (оптимальных) вариантов, в следующем шаге приходится просматривать их _все_, чтобы найти в конце концов оптимальное решение. Так уж оно устроено
А вообще, ПЕРВОЕ, что нужно сделать после получения более-менее работоспособного решения, ето проверить, как оно работает на всяких вырожденных и екстремальных входных данных, допустимых по условию задачи. Я как составитель нескольких олимпиадных задач (да и все мне известные составители тоже ) _всегда_ делал такие тесты. |
Сообщ.
#5
,
|
|
|
Цитата Visitor, 29.12.03, 09:33 Просто когда на очередном шаге етого самого динамического программирования получается _много_ одинаковых по стоимости (оптимальных) вариантов, в следующем шаге приходится просматривать их _все_, чтобы найти в конце концов оптимальное решение. Тобишь что бы удостовериться, что на втором ходу я сделал правильный выбор, тобишь взял 4, мне нужно перерыть всю! последовательность до конца, причем на каждой такой развилке удваивать кол-во перебора оставшихся чисел. При написании ответа у меня в голове бродили мысли что может быть такая вырожденная последовательность, например для таких, выше, данных неполучилось собрать наименьшую сумму если таким подходом выбирать число дающее минимальное приращение суммы. Хотя я не уверен что вообще возможно первому игроку собрать наименьшую сумму. Во всяком случае этот алгоритм можно назвать эвристическим, а не переборным. И он точно не подвиснет на 200 единицах Потому что не имеет рекурсии. Цитата Visitor, 29.12.03, 09:33 Я как составитель нескольких олимпиадных задач А вот это интересно хотел бы почитать условие, надеюсь это не N-мерные кубы ? |
Сообщ.
#6
,
|
|
|
Не надо перерывать всю... Я ж говорю -- динамическое программирование. Если ты знаешь свои и противника оптимальные ходы и ожидаемый результат на (всех) подпоследовательностях длины 5, ты достаточно просто определишь их для подпоследовательностей длины 6...
ВТОРЫЕ почти правильные сабмиты решений вылетали обычно из-за того, что разрядности используемых промежуточных переменных не хватало для хранения промежуточных результатов. Хотя здесь, вроде бы, ето составитель предусмотрел, и такого еффекта быть не должно... Мы своих не жалели Задачи... Вот, оказывается, в инете отчет разместили по одному из мероприятий http://rtf.ustu.ru/OL_HTM/Olymp.htm |
Сообщ.
#7
,
|
|
|
Игра имеет всего N^2 состояний.
Строим таблицу и заполняем от конечных к начальным. |