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

Автор feruz.atamuradov, история, 7 лет назад, По-русски

Помагите мне пожалуйста как решить эту задача Шары и коробки

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

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

Давай посчитаем динамику:

dp[i][j][k] — ответ для i — коробок, где в данный момент осталось j красных и k синих шаров.

Тогда персчитывается вот таким образом:

Переберем двумя циклами числа x, y. x — означает количество красных шаров, которые мы положим в i-ю коробку, а y количество синих шаров, которые мы положим в i-ю коробку.

Тогда в состояние dp[i][j][k] мы приходим из состояния dp[i - 1][j + x][k + y].

Код:

Click
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

1) Синие шары никак не зависят от красных. Посчитаем, сколькомя способами можно разложить красные шары, сколькомя способами можно разложить синие шары, перемножим результаты. Это и будет ответ.

2) Посмотрим сколькомя способами можно разложить не более чем A шаров в N коробок. Утверждение: есть ровно C(N+A,A) различных разложений. Доказательство: Допустим, нам нужно разложить ровно A шаров. Тогда есть ровно C(N+A-1,N-1) способов добится этого. Как это получить: представим себе N+A-1 предмет. Каждый предмет это или шар, или перегородка между коробками. Заметим, что различные расположения перегородок однозначно определяют различные разложения шаров по коробкам. Всего есть C(N+A-1,N-1) способов выбрать перегородку.

Нам же нужно разложить не более чем A шаров. Для этого просто добавим фиктивную N+1-ую коробку, в которую пойдут все не разложенные ранее шары. Получим формулу C(N+A, A).

Код