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

Задача на ДП
Автор Karaev_Marik, история, 9 лет назад, По-русски

Привет всем! Решаю вот эту вот задачу ссылка Придумал только вот какое решение. Считаем dp[i]-максимальная выручка за за первые i дней. Переход dp[i]=max(0<=j<=i: dp[j]+c[i]*(pref[i]-pref[j])), то есть перебираем когда в последний раз нам выгодно рубить дерево и выбираем оптимальный. Здесь pref[k]-на сколько вырастет бамбук за первые k дней. Но, это О(n^2). Как решить эту задачу за O(n)?

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

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

Жадность. Если нет j > i такого, что c[j] > c[i], то выгодно срезать весь бамбук и продать. Проверять наличие такого j можно, предподсчитав максимумы на суффиксах за O(n). http://pastebin.com/Wjeq4Bgg

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

спасибо... вообще как можно отличить в каких задачах жадность, а в каких динамика?

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

    Если был бы какой-то алгоритм, хорошие программисты ценились бы куда меньше.

    Нужно просто решать много задач и учиться находить такие идеи.

    → Ответить