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

## 题意 ##

n个人，每个人对上谁都有胜负。现在问如何安排比赛，输出每个人最后的胜利的情况数。

## 思路 ##

唐老师原话。

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

TC的官方题解

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.

简单地说，对于某个状态S，我们可以把它分成两组，从每组里面各找出一个人对决，加上之前的子状态那个人赢的数目。

## 代码 ##

class CheeseRolling {
public:
    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)
                cur_state.push_back(j);
            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)
                    substate.push_back(j);
                for (int j = 0; j < n; j++) if (!((s>>j)&1) && ((i>>j)&1))
                    remain_person.push_back(j);
                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;
    }
};

• 上一篇 Project Euler
• 下一篇 Python 练习册，每天一个小程序