Помагите мне пожалуйста как решить эту задача Шары и коробки
Помагите мне пожалуйста как решить эту задача Шары и коробки
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
| Название |
|---|



Давай посчитаем динамику:
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).
Код