HDU3811 Permutation —— 状压DP

2018/03/06 14:54
阅读数 34

题目链接:https://vjudge.net/problem/HDU-3811

 

Permutation

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 496    Accepted Submission(s): 238


Problem Description
In combinatorics a permutation of a set S with N elements is a listing of the elements of S in some order (each element occurring exactly once). There are N! permutations of a set which has N elements. For example, there are six permutations of the set {1,2,3}, namely [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 
But Bob think that some permutations are more beautiful than others. Bob write some pairs of integers(Ai, Bi) to distinguish beautiful permutations from ordinary ones. A permutation is considered beautiful if and only if for some i the Ai-th element of it is Bi. We want to know how many permutations of set {1, 2, ...., N} are beautiful.
 

 

Input
The first line contains an integer T indicating the number of test cases.
There are two integers N and M in the first line of each test case. M lines follow, the i-th line contains two integers Ai and Bi.

Technical Specification
1. 1 <= T <= 50
2. 1 <= N <= 17
3. 1 <= M <= N*N
4. 1 <= Ai, Bi <= N
 

 

Output
For each test case, output the case number first. Then output the number of beautiful permutations in a line.
 

 

Sample Input
3 3 2 1 1 2 1 3 2 1 1 2 2 4 3 1 1 1 2 1 3
 

 

Sample Output
Case 1: 4 Case 2: 3 Case 3: 18
 

 

Author
hanshuai
 

 

Source
 

 

Recommend
lcy
 
 
题意:
给出m个(A,B),问n的全排列中有多少个满足:至少存在一个i,使得第Ai位为Bi?
 
 
题解:
1.状压DP,设dp[status][has]为:状态为status(前面含有哪几个数),且是否已经满足要求(has)的情况下有多少种。
2.剩下的就是类似TSP的状态转移了(感觉又像是TSP,又像是数位DP)。
 
 
代码如下:
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const double EPS = 1e-6;
15 const int INF = 2e9;
16 const LL LNF = 9e18;
17 const int MOD = 1e5;
18 const int MAXN = (1<<17)+10;
19 
20 bool g[20][20];
21 LL dp[MAXN][2];
22 int cnt[MAXN];
23 
24 void init()
25 {
26     for(int s = 0; s<MAXN; s++)
27     {
28         cnt[s] = 0;
29         for(int j = 0; j<17; j++)
30             if(s&(1<<j)) cnt[s]++;
31     }
32 }
33 
34 int main()
35 {
36     init();
37     int T, n, m, kase = 0;
38     scanf("%d", &T);
39     while(T--)
40     {
41         scanf("%d%d", &n, &m);
42         memset(g, false, sizeof(g));
43         for(int i = 1; i<=m; i++)
44         {
45             int u, v;
46             scanf("%d%d", &u, &v);
47             g[u][v] = true;
48         }
49 
50         memset(dp, 0, sizeof(dp));
51         dp[0][0] = 1;
52         for(int s = 0; s<(1<<n); s++)
53         {
54             for(int i = 0; i<2; i++)
55             {
56                 for(int j = 0; j<n; j++)
57                 if(!(s&(1<<j)))
58                     dp[s|(1<<j)][i|g[cnt[s]+1][j+1]] += dp[s][i];
59             }
60         }
61         printf("Case %d: %lld\n", ++kase, dp[(1<<n)-1][1]);
62     }
63 }
View Code

 

 

 

 

 

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部