Подскажите в какую сторону думать )

[breate]

я считаю что не самым точным но самым быстрым будет
1 найти минимальный элемент каждой строки
2 посчитать каких элементов больше(примерно среднее арифметическое) с учетом отклонения +/-1
3 найти сумму

всего будет сделано n + 1 проходов по матрице

3____2____8____6____4 min 2
4____7____12___9____1 min 5
55___8____3____2____8 min 4
20___7____4____9____1 min 5

явно видно доминирование 5-го столбца над всеми

[LeBron]

Во-первых, асимптотика та же. Во-вторых, полный бред, так как нету алгоритмического обоснования - я даже не увидел в Вашем посте, чему равен ответ, скажем, для примера. В-третьих, проход по матрице будет 1. В-четвертых, повторю еще раз, решение, приведенное мною - полноценное и алгоритмически эталонное, вопрос только в пряморукой реализации. У кого вопросы - купите себе хотя бы сборник алгоритмов. В-пятых, нужно не "не самое точное", а ПОЛНОЕ решение, поэтому ваше заслуживает только на место на баше - примерные решения это марафон на топкодере, а не олимпиадная задача, в которой тестирование ведется по принципу "совпало - зачет, не совпало - незачет".

[Airo]

Спасибо LeBron! Отличный способ решения, незнаю сколько бы у меня ушло времени додуматься до этого (думал только рекурсия подойдет). Правда не очень понял про массив указателей путей Пошел по своему пути, из нового массива иду снизу вверх от наименьшего элемента и запоминаю координаты которые потом применю к заданному массиву.
Еще вопрос, я впервые услышал (от тебя) понятие - динамическое решение, можешь объяснить где оно тут проявляется, просто задача как задача.. И извени если достаю =)

[LeBron]

Нет, не достаете. Вполне нормальные вопросы, которые нормально сформулированны и поставленны. Динамическое программирвание - даже не знаю, как объяснить. Есть формальные определения, можно в Вики почитать, коротко я не объясню. В задачах такого типа - определяется как разбиение задачи на простые подзадачи, доказательство их индуктивной коректности и поочередное решение. В конкретном случае - мы задачу "найти путь к енной строке" разбили на "найти путь к первой строке", "найти пусть с первой строки во вторую", и так делее. Часто используется, когда трудно в зависимостях найти определенную формулу, но можно делать индуктивно. Например, мы не знаем, чему равно f(x). но доказали, что f(x)=g(f(x-1)). Зная f(1), можем в цыкле или рекурсией найти сначала f(2), потом f(3), и так до искомого.
Еще случай - задача о ранце. Есть грузоподъемность ранца и массив весов возможных предметов, которые в него можно сунуть в любом количестве. Надо определить, можно ли заполнить ранец ровно по грузоподъемности. Простой перебор или рекурсия убиваются, а надо делать почти так же, как в прошлом примере - заводим массив "можно-нельзя". 0ой эллемент делаем 1 "можно", так как пустой ранец (вес 0) - не проблема. А дальше в цикле с 0 если эллемент "можно", то и все, которые "можно+любой из весов из массива" тоже "можно". Если эллемент не стал можно, пока мы до него добирались - он "нельзя". Снова получилось определять функцию через более низкие аргументы
По поводу указателей - в дополнительном массиве хранить для каждой клетки, откуда в нее надо прийти для минимального пути. Вот здесь можно для самого вывода уже и рекурсию использовать, если есть желание.

[LeBron]

Airo, Ваше решение задачи поиска пути немногим хуже, чем мое, а в плане памяти - даже лучше. Просто у меня для каждой клетки будет извесно, как в нее прийти, а у Вас уйдет 3 действия (как я понял, Вы для клетки массива сум будете выбирать минимальную клетку массива сум, из которой можна в нее прийти), что не много, но зато память ненужную вы не используете, а я использую. Какое из 2 решений выбрать - нужно всегда смотреть в конкретном случае (по ограничениях и возможностях), но знать и уметь пользоватся надо обеими.

[rand8154]

Мне понравлся неизвращенный и трезвый ход Вашых мыслей.
Может немного не по теме, но хочу спросить: есть ли красивая идея реализации зеркального отображения числа вида 011->110, 01011100111->11100111010 т.п. без тупого цикла?

[LeBron]

Сообщение от rand8154

Мне понравлся неизвращенный и трезвый ход Вашых мыслей.
Может немного не по теме, но хочу спросить: есть ли красивая идея реализации зеркального отображения числа вида 011->110, 01011100111->11100111010 т.п. без тупого цикла?

Зависит от того, что называть тупым циклом. Я бы просто сделал цикл (тупой?), в котором через дополнительный массив сделал бы посимвольно "зеркальное отражение". Если хотите определенный "математический факт", то я его с ходу не вижу. А вдумываться глубше просто не вижу смысла.