Developing.ru

Всем привет! Помогите пожалуйста решить хитрую задачку! у самой ничего не получается..Заранее огромное Вам спасибо!!! Задача решается через вектора..

Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на N*N (N<=50) клеток, находится один комар весом aij (вес комара – натуральное число <= 50), i - номер строки, j - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна N. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.

Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.

Входные данные

Первая строка входного файла INPUT.TXT содержит число N. Следующие N строк содержат по N чисел aij, разделенных пробелами.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – вес съеденных комаров.

Примеры

INPUT.TXT OUTPUT.TXT
3
8 2 1
1 2 6
2 7 2 14
5
8 2 1 2 3
1 2 6 2 4
2 7 2 3 4
1 3 2 4 4
1 3 4 3 1 19

Перенёс в алгоритмы, так как задача привязана не столько к языку, сколько необходимо нахождение изящного алгоритма, который будет более быстр, чем полный перебор. Мне с первого взгляда кроме полного перебора ничего в голову не приходит. Попробую позже подумать над задачей, может осенит.

Romeo писал(а):Перенёс в алгоритмы, так как задача привязана не столько к языку, сколько необходимо нахождение изящного алгоритма, который будет более быстр, чем полный перебор. Мне с первого взгляда кроме полного перебора ничего в голову не приходит. Попробую позже подумать над задачей, может осенит.

Огромное спасибо Вам! Я думаю возможно такой алгоритм!?
1 цикл - перебираем столбцы исходной матрицы
2 цикл - перебираем массив сумм
3 цикл - перебираем столбец исходной матрицы (для каждого значения в массиве сумм ищем в столбце лучший вариант)

Очевидно комары будут съедаться в основном из верхних строк, т.к. чем меньше номер строки, тем большее число клеток мы сможем охватить. Наверное было бы неплохо предварительно значения в матрице с весом комаров построчно поделить на номер строки, тем самым узнав реально эффективный вес. А дальше строим допустимые маршруты и считаем суммы. Имхо только перебором, т.к. комбинаторика на лицо.