Could anyone please explain to me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_o Please help?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | -is-this-fft- | 161 |
3 | maomao90 | 159 |
3 | atcoder_official | 159 |
5 | cry | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
Could anyone please explain to me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_o Please help?
Name |
---|
dp[i][mask] = Number of ways to match first i men with the set of women indicated by the mask, 0 <= i <= n, 0 <= mask <= 2^n. Obviuosly, if i != popcount(mask), dp[i][mask] = 0.
Fill the dp table by iterating over i and mask. When you fill dp[i][mask], you iterate over all possible pairing of i-th man with a woman. So the transition is dp[i][mask] = (sum of dp[i-1][mask ^ 1 << j] where j-th woman appeared in the mask). Code
Oof I implemented the same method in recursive way and it got TLE
my recursive solution with similar approach got accepted (1.2sec) https://atcoder.jp/contests/dp/submissions/47816603
You can refer to explanation by FlowerOfSorrow(above comment) and this code — https://atcoder.jp/contests/dp/submissions/15835680