Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


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

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru