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

Задача на дп
Автор i_luve_you, история, 4 года назад, По-русски

Есть задача на дпшку, знаю только решение на куб, подскажите как решить за квадрат.

Василий решил построить забор вокруг своего дачного участка, чтобы забор был нескучным он решил что каждая доска в заборе должна иметь различную высоту. У него есть доска длины N, он хочет узнать сколько существует способов разрезать её на куски с различными целочисленными длинами, вся длина доски должна быть истрачена.

Входные данные В первой строке дано единственное целое число N (1≤N≤5e3) — длина исходной доски.

Выходные данные Выведите единственное целое число — количество способов разрезать исходную доску на куски различной длины. Так как результат может быть очень велик выведите его по модулю 1e9+7.

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

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

Заведем двумерный массив dp[i][j] — сколько способов порезать первые i метров доски так, чтобы последняя часть была длиной j. Тогда dp[i][j] = сумма всех dp[i-j-1][k], 1 <= k <= i-j-1. Заводишь массив sum[i] = сумма всех dp[i][k], 1 <= k <= i. Таким образом ты можешь считать все dp[i][j] за квадрат. Ответ это sum[n]

P.S Решение сверху неверно). Поздно вспомнил про ограничение в различные доски.

→ Ответить
»
4 года назад, # |
← Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

dp[1] = 1, dp[i] = dp[i - 1] * 2

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

Заведем двумерный массив dp[i][j] — сколько способов порезать первые i метров доски так, чтобы последняя доска была длиной j. Тогда dp[i][j] = сумма всех dp[i — j][k], k < j. Будем делать ДП вперед. Допустим мы уже знаем dp[i][j] для зафиксированного i, тогда фором перебираем j (длина следующей доски) и поддерживаем sum (сумма dp[i][k], k < j), тогда переход такой

for(1 <= j <= n)
{
    dp[i + j][j] += sum;
    sum += dp[i][j];
}

Ответ это сумма dp[n][j], 1 <= j <= n

Код — https://ideone.com/ADpCLh

P.S у меня ушло 6 недель, чтобы решить эту задачу. Можно ссылку?

→ Ответить