dancing couples

topCoder: DancingCouples editorial
"Each subproblem is clearly defined by three variables: the set of unmatched boys, the set of unmatched girls, and the number of couples we need to make."

d[i][j][k]  ----- the total ways to make k couples 
  |  |  |
  |  |  i couples to make
  |  available girl status (bitmask)
  the i-th boy to match

d[i][j][k] = the ways to make k couples in which we do not use the i-th boy +
             the ways to make k couples in which we use the i-th boy
           = d[i-1][j][k] + sum (d[i-1][j^(1 << k)][k-1])
                         {k|A[k][j]='Y'}

对比上一贴：

cnt [v][s] = the ways in which z6 = 0 + the ways in which z6 > 0
           = cnt[v-1][s] + cnt[v][s-v]

The code:

int dp[12][1025][12];
int solve(int nboy, int available_girl, int K) {
    if(nboy < K || count_bit(available_girl) < K) return 0;
    if(K == 0) return 1;
    if(dp[nboy][available_girl][K] >= 0) return dp[nboy][available_girl][K];

    int res = solve(nboy-1, available_girl, K);

    for(int i = 0; i < cd[0].size(); ++i) {
        if(cd[nboy-1][i] == 'Y' && available_girl & (1<<i))
            res += solve(nboy-1, available_girl ^ (1<<i), K-1);
    }
    return dp[nboy][available_girl][K] = res;
}