TopCoder SRM 663 Div2 Problem 1000 - CheeseRolling (状压dp)

Sep 22, 2015

## 题意 ##


## 思路 ##


点集为 i 胜者为 j 的方案数 实际上有用的状态不多 i里的点数是2的幂次 然后枚举i的子集s,使得s点数是i的一半,t=i xor s,也就是补集,枚举两个子集里的胜者,然后将方案数加到两个胜者比赛后的胜者里。


What we can do is represent this as f(i,S), where i is the player in question and S the set of players available in this tournament. We want to play with recursion so we need a way to divide the problem into smaller versions of this problem. Consider this: An elimination tournament of 16 players can be seen as two tournaments of 8 distinct players each plus a last match between the winners of the two smaller tournaments. When given S players, we want to divide them in two disjoint halves: S1 and S2, the only thing we’ll know about the order is that players in S2 will be ordered after S1. So S1 and S2 will each have one winner. We are interested in scenarios in which player i wins S1 or S2 (Depending of which one i was included in). There are two cases, in one of the cases i is in S1; There are f(i,S1) ways in which i will win S1. For each j in S2, it is possible that j wins the mini-tournament of S2 a total of f(j,S2) times. If according to our match up rules, i wins after matched against j, then we need to add f(i,S1)×f(j,S2) to the final result, because those are the number of ways in which i versus j is the final match in the tournament AND thus ways in which i wins. Consider the cases in which i is in S2. Due to symmetry, this will look exactly the same, so in fact we should be adding 2×f(i,S1)×f(j,S2) to the result.


## 代码 ##

class CheeseRolling {
    LL dp[(1<<17)][17], number_in_state[(1<<17)];
    vector<long long> waysToWin(vector<string> wins) {
        int n = SZ(wins);
        for (int i = 1; i < (1<<n); i++)
            vector<int> cur_state;
            for (int j = 0; j < n; j++) if ((i>>j)&1)
            int sz = SZ(cur_state);
            number_in_state[i] = sz;
            if (sz == 1) dp[i][cur_state[0]] = 1;
            if (sz != 2 && sz != 4 && sz != 8 && sz != 16) continue;
            for (int s = (i-1)&i; s; s = (s-1)&i)
                if (number_in_state[s] != sz / 2) continue;
                vector<int> substate, remain_person;
                for (int j = 0; j < n; j++) if ((s>>j)&1)
                for (int j = 0; j < n; j++) if (!((s>>j)&1) && ((i>>j)&1))
                int ss = i^s;
                for (auto u : substate)
                    for (auto v : remain_person)
                        if (wins[u][v] == 'Y') dp[i][u] += dp[s][u] * dp[ss][v];
                        else dp[i][v] += dp[s][u] * dp[ss][v];
        vector<LL> ans;
        for (int i = 0; i < n; i++) ans.push_back(dp[(1<<n)-1][i]);
        return ans;