Educational Codeforces Round 61 E. Knapsack
https://codeforces.com/contest/1132/problem/E
Using a technique like digit-dp, this problem can be reduced to the 0-1 problem. I define the table dp[2000][1 << 8]. The first index means the remaining weight after taking items. The second index means whether the number of j's is less than C[j] or not. Since we have eight items, 2^8 states are needed. If we run this dp naively, 2000 is not enough to store all information. However, If we take them in descending order, that is 2^50,2^49,2^48,..., then we do not need to maintain the information of lower bits because they are not changed by higher item.
My implementation is a little noisy.
https://codeforces.com/contest/1132/submission/50847802
公式解説は最小公倍数を使っていて賢い。1 は 840 個ずつの束にし、2 は 420 個ずつの束にし、3 は 280 個ずつの束にし、ほかも同じように束にする。つまり、ひとつの束が 840 の値になるように束にする。ただし 2 が 850 個あったとしても、10 個と 2 束にはしない。850 個の正しい分け方は 430 個と 1 束である。430 個と 1 束があればこれらを組み合わせることで 0 個から 850 個のすべてを表せる。このように表せる組合せを変えることなく束にできる。束にならなかった部分をどう組み合わせるかは動的計画法で求めて、そのあと束を足せば答えが得られる。
