|
|
|
|
|
|
|
| 21 Зубашев Степан, 18 ноября 2009 г. 23:40:28 |
вах вах! я таки сдал этого монстра =) оказывается всё эти закономерности которые тут люди (в том числе) и я выводили нафиг не нужны.
подсказка тем кто долго мучается и как я ничего не понимает в ДП:
1 напишите перебор, которые решает все тесты (тл не в счёт)
2 добавте в этот перебор возможно запоминать наилучший выбор (слева взять цифру или справа) для игрока (например int mas[100][100], где mas[start,end] будет хранить наилучший выбор в такой последовательности), и каждый раз натыкаясь в рекурсиях на уже известное растояние не лезть внутрь рекурсии, а брать ответ из этого массива
надеюсь доступно обьяснил. думаю админ именно это имел ввиду когда писал что надо использовать двумерные массивы
да, я имел ввиду именно это. у вас как раз идеи на рекурсивную реализацию нисходящей динамики. программа еще более эффективно работает, если реализовывать восходящую динамику без рекурсии, двойным циклом: получается код короче, работает быстрее, но думать надо чуть-чуть больше. мне тоже кажутся рекурсивные реализации проще, т.к. не приходится задумываться о последовательности вычислений значений.
|
|
|
| 22 Набиев Умед (ТРГИ), 18 сентября 2009 г. 13:49:22 |
админ скажите пж в каждом ходе игрок должен выбирать макс из двух краев?
не всегда выбор максимального с краю приводит к победе
|
|
|
| 23 Kuzmin Alexey Andreevich, 14 января 2009 г. 19:33:45 |
Слабенько для IOI... А почему бы не выводить в этой задаче разницу между счетами 1го и 2го? Задача особо не меняется, то же ДП по подстрокам, но тестить легче (для человека :-) ) Кстати у Вас в условии не сказано, чего же должно быть в сумме больше у победителя. Это конечно и так ясно, но...
Думаю, что самое простое в этой задаче - это догадаться чего больше надо набрать первому игроку ;)
|
|
|
| 24 Сушенцев Игорь, 29 ноября 2008 г. 16:20:49 |
А мне интересно, у Вас в решении используются двумерные массивы?
У меня лично да, вроде как так попроще. Это как-никак нисходящее ДП.
|
|
|
| 25 Сушенцев Игорь, 29 ноября 2008 г. 16:18:15 |
| Блин, само решение(причем соблюдая структуру) < 15 строк, а проходит!
|
|
|
| 26 Умед, 11 ноября 2007 г. 8:57:19 |
Зачем врать?! Эта задача была на Международной олимпиаде в 96 году! и Степанов правильно сказал.
Я не вру, что я ее придумал. Просто часто придумываешь "велосипед". Наверное, не сложная задачка для международной олимпиады-то...
|
|
|
| 27 Степанов Егор Владимирович, 30 октября 2007 г. 13:51:54 |
по-моему, похожая задачка была на каком-то из межнаров
по-моему, я ее сам придумал, доработав более простую задачу
|
|
|
| 28 TRGI "Hotam & P.V.", 26 сентября 2007 г. 21:57:26 |
Почему на первом примере 8 и 6? Должно получиться 7 и 7, если они оба играют хорошо?
Потому и получается что 8 и 6, т.к. они хорошо играют. Если бы играли так же плохо как Вы, то могли бы набрать 7 и 7, а могли и еще чего хуже :) Объясню: поскольку первый игрок играет хорошо, то он возьмет не 4ку, а 3ку слева, тогда что бы ни взял 2й игрок, как бы он это ни сделал хорошо, 1му игроку достанется 5, а значит в сумме он наберет 8. От игрока 2 ничего не зависит, т.к. 1й игрок может поставить 2го в такое положение, что тот ничего не сможет взять кроме 2 и 4. Это очень легко понять.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
