|
|
|
|
|
|
|
| 21 АЗАМОВ АКРАМ АЗАМОВИЧ, 23 декабря 2009 г. 18:51:54 |
kontrprimer:
6 6
2 0 5 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 1 3 0 0 0
|
|
|
| 22 Прищенко Богдан Олегович, 24 июня 2009 г. 17:19:14 |
| да уж:) красивая и простая задача, на такой неплохо обяснять ученикам, что такое динамика, и как ее решать. Тем не менее, я затупил и получал неверный ответ, так как просчитывал все поля... В том числе и последнее, поэтому у меня получался ответ больше, так как тестил на примере, где в последней клетке 0, - я дополнительно считал и варианты, которые заканчиваются переходом с последней клетки на 0 - тоесть, на последнюю:) Народ, не повторяйте эту глупую ошибку.
|
|
|
| 23 Масюк Олег Юрьевич, 16 января 2009 г. 14:05:53 |
Можно поподробнее об кешировании рекурсии, не очень понятно...
Ну это речь о нисходящем динамическом программировании, об этом вы можете прочитать в курсе олимпиадника на этом сайте.
|
|
|
| 24 Esbol Zharlgapov Kairgalievich, 10 ноября 2008 г. 19:38:39 |
a[n,m] всегда равен 0?
это абсолютно не имеет никакого значения. как только вы дошли до этой клетки, то дальше уже идти не надо.
|
|
|
| 25 Кожаев Г.М., 31 июля 2008 г. 7:48:41 |
| Блин, говорит Тайм лимит, я из за этого программу несколько раз переделал, оказывается это из за обращения к несуществующему элементу массива.
|
|
|
| 26 Кожаев Г.М., 30 июля 2008 г. 8:48:51 |
А первый тест отличается от приведенного примера?
Не отличается.
|
|
|
| 27 Ринат Тайжетинов, 18 мая 2008 г. 19:58:21 |
А если рекурсией решать, как её можно оптимизоравать чтобы прошла?
Можно реализовать так назыаемое мной "кеширование рекурсии", т.е. чтобы не вычислять одни и те же значения их можно записывать в двумерный массив и в случае необходимости их использования не вычислять заново, а извлекать из массива.
|
|
|
| 28 Akhmirov Emil, 14 мая 2008 г. 11:11:12 |
А длины шагов могут быть = 0 или отрицательными?
Не могут конечно. Это ясно уже из названия задачи :) Фактически вы спрашиваете: можно ли в задаче "только в право или в низ" оставаться на месте или идти влево или вверх.
|
|
|
| 29 Царицинский Сергей, 20 января 2008 г. 0:52:47 |
А при размерах массива 1х1 какой ответ - 0 или 1?
При данных ограничениях ответ 1. Ведь есть возможность добраться до крайнего правого угла :) Это можно сделать единственным образом: ничего не делая.
|
|
|
| 30 Прокопьев Игорь Юрьевич, 19 января 2008 г. 7:53:38 |
Здесь рекурсия не проходит?
Рекурсия может пройти, если не делать полный перебор. Вообще, это динамическая задача.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
