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

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

HotLog


 
Вернуться
Тема: Задача 1488. Робот. Решил с помощью рекурсии + небольшая оптимизация + мемоизация. Есть решение с помощью формул комбинаторики?
1
  1  Жуков Александр И, 01 апреля 2018 г. 14:59:12
      Спасибо
  2  Меньшиков Фёдор Владимирович, 01 апреля 2018 г. 11:18:55
      Автор вопроса как я понимаю и использовал нисходящее ДП, если упоминал о мемоизации. Вопрос был о том, можно ли без ДП вообще. С помощью ДП без рекурсии эта задача конечно же решается проще, чем через комбинаторику или нисходящее ДП.
  3  Владимир Игоревич Лукьянчиков, 31 марта 2018 г. 19:11:51
      Динамическое программирование.
  4  Меньшиков Фёдор Владимирович, 30 марта 2018 г. 19:23:15
      Чисто комбинаторика вряд ли. А вот перебор (сколько ходов влево) + комбинаторика достаточно. По количеству ходов влево однозначно определяется количество ходов вправо (нужно получить X). По количеству оставшихся команд однозначно определяется количество ходов вверх и вниз так, чтобы было получено Y. А дальше нужно из K элементов выбрать фиксированное количество команд влево, фиксированное количество команд вправо, фиксированное количество команд вниз и фиксированное количество команд вниз. Это уже формула, аналогичная используется в задаче 157 "Карточки".
1

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

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483