Блог пользователя kb.

Timus 1342. Фирма веников не вяжет
Автор kb., 14 лет назад, По-русски
Здравствуйте! Прошу помочь с решением этой непростой для меня задачи.
Несколько наблюдений я все-таки сделал:
  1. Научился вычислять стоимость с 1 по i веник для любого завода за O(1)
  2. Динамика, как мне кажется, будет двумерная, строки - кол-во веников, столбцы - использованные заводы с 1..j, ячейка - минимальная стоимость. A[1, j] и A[i, 1] заполняются очевидно.
Но вот соотношения вывести не получилось... Или вообще неверная у меня идея?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Динамика кажется одномерная. Просто A[i] - равно минимальному денег, чтобы сделать i веников. Идем по фирмам и перебираем кол-во веников, которое будет на этой фирме произведено и улучшаем результат. Естественно нужно хранить 2 состояния динамики текущее и улучшаемое, чтобы одной фирмой многократно не улучшать результат. Итого сложность будет O(N*M*K)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
То есть для каждой ячейки перебираем все фирмы и пробуем произвести j = 1, 2, ..., i веников, стоимость будет равна сумме стоимости производства j веников на фабрике и A[i-j]? Или я неправильно понял?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Для каждой фирмы, перебираем уже имеющееся кол-во веников - i =1,2..n и пробуем произвести j=1,2..k веников. Результат будет Anext[i+j]=min(Anext[i+j],Acur[i]+Cost(j веников)).
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Огромное спасибо за объяснение! Правда, задачу так и не сдал, WA16, но это скорее всего уже мои реализационные косяки :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Фирма Фенвиков не вяжет. o_O
→ Ответить