Цитата(klem4 @ 25.01.2006 16:48)
Извиняюсь за серость, это об оперативной памяти речь идет ?
О ней, родимой. Динамическое программирование (ДП) заключается в том, что ты запоминаешь промежуточные результаты, которые не нужны собственно для окончательно ответа, но потребуются при продолжении расчетов. Поскольку надобятся они в произвольном порядке, то класть это в файл на диск нельзя. Но это ускоряет вычисления (пока хватает памяти). Простейший пример: допустим, тебе в расчетах нужен факториал. Ты пишешь функцию с обычным перемножением чисел. Сначала тебе нужен 20!, потом 15!, потом типа 30! ... Можно все вычислять честно, но тогда на каждом вычислении нужно производить все умножения. А можно иначе: вычислил, скажем, 20! - и запомнил.. Потом, когда понадобился 30! - вынул и домножил на десять чисел. И тоже запомнил - пригодится, когда будет вычисляться типа 33! Это, конечно, очень простой пример..
Цитата(hardcase @ 25.01.2006 17:13)
Брутфорс расстановок....
Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20...
Мне так не сдается. Условия слишком специфические, никаких общих принципов тут не присобачишь. Подумай, конечно - может, я что упустил.. Но, судя по тому, что она давалась setare как объект для ДП, я все же прав..
Цитата(hardcase @ 25.01.2006 17:13)
Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми.
Перебор есть перебор, и перебирать надо все. Там все слишком завязано на нижнем уровне, оптимизировать не получается (у меня). Для того, чтобы в этом убедиться (или меня разубедить), нужно поиграть с условиями в уме.
Цитата(hardcase @ 25.01.2006 17:13)
Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ.
Значит, решать нужно без ДП. Но 20х20 - терпимо. На моей машинке (двойной Athlon MP 2200+) этот размер пролетал за секунды. Введение двумерности усложнит расчет раза в три-четыре (не больше порядка, это точно) на каждой строке, да умножить на кол-во строк.. Короче, вполне терпимо еще, на ночь оставлять не потребуется
Задачка действительно неплохая, респект!