| 1 Иванов Иван Иванович, 18 июля 2018 г. 14:14:34 |
| Тяжело дойти до решения. И всё-таки это двумерная динамика. v[i][j] - максимальный вес комара, i - количество посещённых столбцов, j - сумма номеров строк. И ещё: мы можем не есть комара в ячейке. Согласен с Ивановым Иваном Ивановичем насчёт циклов: первый цикл - идём по количеству посещённых столбцов, второй цикл - идём по сумме номеров посещённых строк, т.е. это перебираются индексы для двумерной динамики. Третий цикл - ищем строчку, в которой можно съесть комара с учётом ранее набранных килограммов комаров.
|
|
|
|
|
| 2 Богдан, 21 июня 2018 г. 17:19:11 |
| Отличная задача на дп!
|
|
|
| 3 Слуцкий Алексей, 26 декабря 2016 г. 10:00:15 |
3
5 1 6
2 4 8
4 2 3
Ответ:
13
|
|
|
| 4 Нурахан Арлан Жомартович, 03 февраля 2016 г. 12:32:52 |
| менять циклы действительно помогает
|
|
|
| 5 Гимадутдинов Рустем, 21 октября 2015 г. 12:47:08 |
| Двумерная динамика. По времени O(N^3)
|
|
|
| 6 Денис Розимовский, 12 октября 2015 г. 22:28:12 |
| N^5 :)
|
|
|
| 7 Иванов Иван Иванович, 09 октября 2014 г. 20:59:19 |
Блин, тупил. Просто поменял 2-й и 3-й циклы.
1 цикл - перебираем столбцы исходной матрицы
2 цикл - перебираем массив сумм
3 цикл - перебираем столбец исходной матрицы (для каждого значения в массиве сумм ищем в столбце лучший вариант)
Объяснил как смог.
|
|
|
| 8 Павлов Михаил Валерьевич, 29 апреля 2014 г. 12:50:21 |
| Задача не из самых простых, пришлось подумать. Кроме как за N^3 ничего не придумал. Кода меньше чем в "Копилке", например, но динамика не такая очевидная.
|
|
|
| 9 Назарбек, 16 января 2014 г. 8:41:47 |
Из первого столбца, берем 8 (первая строка)
Из второго столбца ничего не берем.
Из третьего столбца берем 6 (вторая строка)
Вес комаров - 14.
Сумма строк - 1 + 2 = 3 = N.
|
|
|
| 10 Жусубалиев Зарлык, 28 ноября 2013 г. 8:39:05 |
| администратор можете ли вы объяснить первый пример, а то понял как тут 14 получилось
|
|
|
| 11 Костливцев Никита Алексеевич, 29 января 2013 г. 20:59:31 |
| дааа, задача заставляет подумать над ней, впринципе понять алгоритм в ней пол дела, а вот найти в ней кучу подводных камней - задача не из лёгких.
|
|
|
| 12 Яруллин Рамиль Ильдарович, 30 сентября 2011 г. 21:30:04 |
| классная задача!
|
|
|
| 13 Челноков Арсений Андреевич, 12 августа 2011 г. 18:48:18 |
если немного подумать то динамика вообще очевидная)
а сначала показалась что сложная задача!
|
|
|
| 14 Пересадин Илья, 28 июля 2011 г. 14:18:33 |
| что то мне подсказывает, что эта задача сложнее, чем например, задача шоколадка, но сложность ее почему-то меньше
|
|
|
