MERCURY127
Platinum Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору ну давайте для начала уточним условия задачи... »»» Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. 1) в какой клетке Л сидит вначале? что делать с тем комаром, который уже есть в этой клетке на момент начала игры? 2) Л прыгает только между соседними столбцами, только в одном направлении, или может прыгать в любом порядке? 3) что, если мы прыгнули, но не хотим есть комара? можно ли тогда прыгать на уже посещенные столбцы? далее... »»» сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна N »»» Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам. как уже сказали выше, теоретический предел 50*N: имеем N комаров массой 50 в первой строке, прыгаем по ней от первого столбца до последнего. или нужно найти максимум для данной конкретной матрицы? перебором нужно решить, что ли? тогда придется перебрать от N/2 до N! (факториал) вариантов... может, даже с рекурсией... как я это себе представляю... 1) нельзя тупо жрать самых массивных комаров, ибо если на строке N > 25 сидит один комар массой 50, а на первой строке N комаров массой 2 — лучше съесть 2N, чем 50. но если N <=25 — тогда это не катит... 2) тогда остается рекурсия... на каждом шаге сводим задачу к матрице N-1. типа как при вычислении определителей... например, вначала матрица 3х3. запоминаем N*(N-1) = 3*2 числе из последних строки/столбца, и вызываем ту же функцию для остатка матрицы 2х2. там придется запомнить 2*1 чисел и вызвать эту же функцию для остатка 1х1, и тогда она просто вернет единственный переданный ей элемент... что делать с возвратом, я честно говоря пока не сообразил... нужно уточнить условия, как было в начале сказано. Добавлено: наврал, с рекурсией перебирать придется даже больше, чем N факториал... это если можно с возвратом на пройденный столбец, без съедания комара. Добавлено: http://acmu.ru/asp/champ/index.asp?main=tasks&id_stage=241 задача Д, 1 сек и 16 МБ... хоть бы прямо сказали, что мол с олимпиады пришли... нет, спасибо, для олимпиады я слишком туп. я могу рисовать цветные треугольники на ассемблере, но олимпиады — это не мое.
---------- Демагог-прикладник. |
|