[UVA][dp] 12030 - Help the Winners
Help the Winners
| 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;
}