Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Петухов Алексей Владимирович, 16 марта 2019 г. 20:09:34
     Спойлер: dp[start][end][last], если last == 2 - ходил второй, иначе первый(сейчас ход первого и второго соответственно). Первый пытается максимизировать значение dp, второй - минимизировать.
  2  Николай, 31 августа 2018 г. 14:59:19
     Самая интересная задача на дп, которую я решал. Спасибо автору. Еще бы не помешало восстановление ответа.
     В играх плохо восстанавливать ответ, потому что играют двое, и противник вообще говоря играет непредсказуемо. Максимум что можно сделать в такой ситуации - если выиграет первый игрок, попросить указать первый ход, приводящий к выигрышу.
  3  Глубокий Станислав Сергеевич, 23 августа 2016 г. 20:37:04
     Ребята, не пытайтесь найти какие-то правила оптимальной игры. Это ДП, которое (по крайней мере, у меня) сводится к тому, что игрок перед ходом должен знать, сколько он наберет очков, если выберет правый/левый элемент. Надо сравнить сумму очков, которую игрок наберет к концу игры при выборе правого элемента, и сумму очков, которую он наберет к концу игры при выборе левого элемента. Где сумма больше, так ходить и надо.
  4  Баянов В В, 16 июня 2015 г. 12:27:10
     Задача интересная. но не очень сложная и никак не тянет на межнар, (была предложена в 1996 году на межнар олимпиаде), хотя и была самой первой, то есть одной из самых простых.
  5  Бальзин Егор, 19 марта 2015 г. 21:36:24
     Внимание: спойлеры!!!
ans[i][j] - максимальное кол-во денег которое можно набрать в кучках с i-ой по j-ую.
  6  ЛУффи, 17 февраля 2015 г. 9:50:16
     Легче всего решить через динамику по подотрезкам
  7  Васильев Владислав Вячеславович, 09 января 2012 г. 0:15:13
     а как называется эта игра???
     Она без названия, поэтому "Игра - 2" :)
  8  Кравцов Дмитрий, 03 сентября 2010 г. 19:22:00
     Скажите пожалуйста, можно ли решить рекурсией эту задачку?
     Можно, только не полным перебором. Здесь подойдет нисходящая динамика.
  9  Зубашев Степан, 18 ноября 2009 г. 23:40:28
     вах вах! я таки сдал этого монстра =) оказывается всё эти закономерности которые тут люди (в том числе) и я выводили нафиг не нужны.
подсказка тем кто долго мучается и как я ничего не понимает в ДП:
1 напишите перебор, которые решает все тесты (тл не в счёт)
2 добавте в этот перебор возможно запоминать наилучший выбор (слева взять цифру или справа) для игрока (например int mas[100][100], где mas[start,end] будет хранить наилучший выбор в такой последовательности), и каждый раз натыкаясь в рекурсиях на уже известное растояние не лезть внутрь рекурсии, а брать ответ из этого массива

надеюсь доступно обьяснил. думаю админ именно это имел ввиду когда писал что надо использовать двумерные массивы
     да, я имел ввиду именно это. у вас как раз идеи на рекурсивную реализацию нисходящей динамики. программа еще более эффективно работает, если реализовывать восходящую динамику без рекурсии, двойным циклом: получается код короче, работает быстрее, но думать надо чуть-чуть больше. мне тоже кажутся рекурсивные реализации проще, т.к. не приходится задумываться о последовательности вычислений значений.
  10  Набиев Умед (ТРГИ), 18 сентября 2009 г. 13:49:22
     админ скажите пж в каждом ходе игрок должен выбирать макс из двух краев?
     не всегда выбор максимального с краю приводит к победе
  11  Kuzmin Alexey Andreevich, 14 января 2009 г. 19:33:45
     Слабенько для IOI... А почему бы не выводить в этой задаче разницу между счетами 1го и 2го? Задача особо не меняется, то же ДП по подстрокам, но тестить легче (для человека :-) ) Кстати у Вас в условии не сказано, чего же должно быть в сумме больше у победителя. Это конечно и так ясно, но...
     Думаю, что самое простое в этой задаче - это догадаться чего больше надо набрать первому игроку ;)
  12  Сушенцев Игорь, 29 ноября 2008 г. 16:20:49
     А мне интересно, у Вас в решении используются двумерные массивы?
     У меня лично да, вроде как так попроще. Это как-никак нисходящее ДП.
  13  Сушенцев Игорь, 29 ноября 2008 г. 16:18:15
     Блин, само решение(причем соблюдая структуру) < 15 строк, а проходит!
  14  Умед, 11 ноября 2007 г. 8:57:19
     Зачем врать?! Эта задача была на Международной олимпиаде в 96 году! и Степанов правильно сказал.
     Я не вру, что я ее придумал. Просто часто придумываешь "велосипед". Наверное, не сложная задачка для международной олимпиады-то...
  15  Степанов Егор Владимирович, 30 октября 2007 г. 13:51:54
     по-моему, похожая задачка была на каком-то из межнаров
     по-моему, я ее сам придумал, доработав более простую задачу
  16  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. Это очень легко понять.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru