[UVA][dp] 12030 - Help the Winners＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-07-05 12:07:40| 人815| 回0 | 上一篇 | 下一篇

[UVA][dp] 12030 - Help the Winners

推 0 收藏 0 0 站台

Help the Winners

The Sell N' Profit shop has recently had a raffle contest with a prize of a dress and matching shoes to some of their regular customers. They have set aside an equal number of dresses and pairs of shoes of different designs for the purpose.

The plan was going quite well until one customer pointed out that not all the dresses and all the pairs of shoes match each other (i.e. you won't look good if you wore that dress and that pair of shoes at the same time - but the same dress or shoes might look good with something else). So, simply giving someone a dress and a pair of shoes at random, risks angering their customers. They have to give each winner a dress and shoes that match. But some pairs of (dress, shoes) are so adorable to girls such that if they are given to any girl, she would be happier than ever and she may become a great customer of the shop. These pairs are called super matching pairs. But, choosing such pair may lead to a situation that some other girls get non-matching (dress, shoes) pairs.

Now you are given n dresses and n pairs of shoes, a list of what dress matches which shoes and some super matching (dress, shoes) pairs. As the company have lack of fashion sense, they ask you to find how many ways there are to make up n sets of dresses and matching shoes, such that either all the girls are happy (got matching dress and shoes), or at least one of the girls got a super matching pair.

Input

Input starts with an integer T (

100), denoting the number of test cases.

Each case starts with an integer n ( 1n15) by itself on a line, denoting the number of dresses and pair of shoes. Each of the next n lines contains n space separated integers (one of 0, 1 or 2). The j-th integer in i-th line represents the status of the i-th dress and j-th pair of shoes. 0 means that i-th dress doesn't match j-th pair of shoes. 1 means they match. 2 means they are super matching.

Output

For each case, print the case number and number of ways you can form N sets of dresses and shoes.

Sample Input

2 3 0 1 1 1 1 0 1 0 1 3 1 1 2 2 1 0 1 1 2

Sample Output

Case 1: 2 Case 2: 4

目描述：

要找到策略都有得匹配，或者其中一得到 super 匹配(而其他有匹配也)。
匹配的方法。

目解法：

全部匹配最多答案是 "15!"

由於 n <= 15, 可以使用(bitmask)。
依序匹配，且根剩可使用的，的方法。
匹配到重覆的，便可以直接回。

#include <stdio.h>
#include <string.h>
long long dp[1<<15][2][2];
int n, g[16][16];
long long dfs(int idx, int state, int super, int m) {
    if(idx == n) {
        if(super || m) return 1;
        return 0;
    }
    long long &val = dp[state][super][m];
    if(val != -1) return val;
    val = 0;
    int i, tm, ts;
    for(i = 0; i < n; i++) {
        if(((state>>i)&1) == 0) {
            ts = g[idx][i] == 2 || super;
            tm = g[idx][i]&m;
            val += dfs(idx+1, state|(1<<i), ts, tm);
        }
    }
    return val;
}
int main() {
    int testcase, cases = 0;
    int i, j;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        memset(dp, -1, sizeof(dp));
        printf("Case %d: %lld\n", ++cases, dfs(0, 0, 0, 1));
    }
    return 0;
}