Помагите мне пожалуйста как решить эту задача Шары и коробки
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Помагите мне пожалуйста как решить эту задача Шары и коробки
Название |
---|
Давай посчитаем динамику:
dp[i][j][k]
— ответ дляi
— коробок, где в данный момент осталосьj
красных иk
синих шаров.Тогда персчитывается вот таким образом:
Переберем двумя циклами числа
x
,y
.x
— означает количество красных шаров, которые мы положим в i-ю коробку, аy
количество синих шаров, которые мы положим в i-ю коробку.Тогда в состояние
dp[i][j][k]
мы приходим из состоянияdp[i - 1][j + x][k + y]
.Код:
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).
Код