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

Автор iamsardorbek, история, 8 лет назад, По-русски

_Всем привет! Нужна помощь в решении задачи Смотрел решения других, но не очень понятно, когда они делают типа F[i-D[j]] и такое _**** Условие задачи

A. Разрежь ленточку ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт вводстандартный ввод выводстандартный вывод У Поликарпа есть ленточка длины n. Он хочет разрезать ее так, чтобы выполнялись два условия:

После разрезания, каждый кусочек ленточки должен быть длины a, b или c. Количество кусочков ленточки после разрезания должно быть как можно больше. Помогите Поликарпу, найдите количество кусочков ленточки после требуемого разрезания.

Входные данные В первой строке записано через пробел четыре целых числа n, a, b и c (1 ≤ n, a, b, c ≤ 4000) — длина исходной ленточки и разрешенные длины кусочков ленточки после разрезания, соответственно. Числа a, b и c могут совпадать.

Выходные данные Выведите одно число — максимально возможное количество кусочков ленточки. Гарантируется, что существует хотя бы одно корректное разрезание ленточки.

Примеры входные данные 5 5 3 2 выходные данные 2 входные данные 7 5 5 2 выходные данные 2 Примечание В первом тестовом примере нужно разрезать ленточку на два кусочка: один из них длины 2, второй длины 3.

Во втором примере нужно разрезать ленточку на два кусочка: один из них длины 5, второй длины 2.

Заранее спасибо)

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

dp[i] — это макс. кол. кусков у которых суммарная длина равна i. В этой задаче каждый кусок должен быть либо длины a, b или c, поэтому наши переходы будут такими

http://pastebin.com/5bmCpPFY

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Почти понял код, но только почему именно так не догнал

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Насколько понял тебе не догнал почему dp[i] = -inf.

      Решение задача основано построение подзадача всех длины ленточик i = 1..n . НО НЕ ВСЕХ этих значениях можно разделить по требование задач (один из a,b,c). Поэтому надо учитывать именно какие длины можно а какие нельзя. В самом деле так должно быть:

      int dp[ MAXN ];
      bool v[ MAXN ];
      ..............
      for(int i= 1; i<=n;++i){  dp[i] = 0; v[i] = false; }
      dp[0] = 0; v[0] = true;// 0 - special case
      
      //Now we build solution for i = 1..n
      for(int i= 1 ; i <= n; ++i)
      {
         // Теперь подумай о последный разрез: этот разрез должен быть один из a ,b OR c.
         //1. Послденый разрез будет `a`, только если  i - a >= 0 И длина (i-a) - МЫ МОЖЕМ ПОСТРОИТЬ РЕШЕНИЕ, то есть v[i-a] == true.
          if (i >= a && v[i-a] == true) { d[i] = max(d[i], 1 + d[i-a]); v[i] = true;}
         
         // 2. ......
          if (i >= b && v[i-b] == true) { d[i] = max(d[i], 1 + d[i-b]); v[i] = true;}
      
        // 3. ......
         if (i>=c && v[i-b] == true){ d[i] = max(d[i], 1 + d[i-c]); v[i] = true;}
      }
      

      А теперь dp[i] = -inf это играет роль v[ ] array.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можете посоветовать какой-то ресурс по изучению дп?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Просто решай побольше задач ДП (можно в Codeforces) если не смог то дорешивай (это очень важно !!!!)

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

сам думай даун