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 |
что то мне подсказывает, что эта задача сложнее, чем например, задача шоколадка, но сложность ее почему-то меньше
|
|
|