Problem Arrangement (狀壓DP)

Problem Arrangement

ZOJ - 3777

The 11th Zhejiang Provincial Collegiate Programming Contest is coming! As a problem setter, Edward is going to arrange the order of the problems. As we know, the arrangement will have a great effect on the result of the contest. For example, it will take more time to finish the first problem if the easiest problem hides in the middle of the problem list.

There are N problems in the contest. Certainly, it's not interesting if the problems are sorted in the order of increasing difficulty. Edward decides to arrange the problems in a different way. After a careful study, he found out that the i-th problem placed in the j-th position will add Pij points of "interesting value" to the contest.

Edward wrote a program which can generate a random permutation of the problems. If the total interesting value of a permutation is larger than or equal to M points, the permutation is acceptable. Edward wants to know the expected times of generation needed to obtain the first acceptable permutation.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N (1 <= N <= 12) and M (1 <= M <= 500).

The next N lines, each line contains N integers. The j-th integer in the i-th line is Pij (0 <= Pij <= 100).

Output

For each test case, output the expected times in the form of irreducible fraction. An irreducible fraction is a fraction in which the numerator and denominator are positive integers and have no other common divisors than 1. If it is impossible to get an acceptable permutation, output "No solution" instead.

Sample Input

2
3 10
2 4 1
3 2 2
4 5 3
2 6
1 3
2 4
      

Sample Output

3/1
No solution      

題意：

　　輸入n和m，接下來一個n*n的矩陣，a[i][j]表示第i道題放在第j個順序做可以加a[i][j]的分數，問做完n道題所得分數大于等于m的機率。用分數表示，分母為上述滿足題意的方案數，分子是總的方案數,輸出最簡形式。

 題解：

　　狀壓DP。因為最多隻有12道題，對于每一道題我們可以枚舉所有位置，看看哪個位置可以放這個題。dp[i][j]表示在i狀态下得分為j的方案數、具體實作看代碼。

1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int casen;
 7 int n,m;
 8 int a[15][15];
 9 int dp[(1<<13)+10][510];
10 int f[15];
11 int gcd(int a,int b)
12 {
13     if(b==0)
14         return a;
15     return gcd(b,a%b);
16 }
17 int main()
18 {
19     f[1]=1;
20     for(int i=2;i<=12;i++)
21         f[i]=f[i-1]*i;
22     cin>>casen;
23     while(casen--)
24     {
25         memset(dp,0,sizeof(dp));
26         scanf("%d%d",&n,&m);
27         for(int i=1;i<=n;i++)
28             for(int j=1;j<=n;j++)
29                 scanf("%d",&a[i][j]);
30         dp[0][0]=1;
31         for(int i=0;i<=(1<<n);i++)//n個位置，一共會有(1<<n)種可能性，為0--((1<<n)-1) 
32         {
33             int cnt=0;//對于每一種位置占有的狀态，cnt記錄有幾個位置被占 
34             for(int j=1;j<=n;j++)
35             {
36                 if(((1<<(j-1))&i)>0)//判斷i的二進制下第j位是否為1 
37                     cnt++;
38             }
39             for(int j=1;j<=n;j++)//看看可以由i狀态轉移到哪些别的狀态 
40             {
41                 if(((1<<(j-1))&i)>0)
42                     continue;//先找出哪些位置沒有被放上題，即下一步我們可以占哪些位置 
43                 for(int k=0;k<=m;k++)
44                 {
45                     if(k+a[cnt+1][j]>=m)//cnt+1的意思是目前狀态已經把前cnt個題放上了，然後現在要放第cnt+1個題 
46                     {
47                         dp[i+(1<<(j-1))][m]+=dp[i][k];
48                     }
49                     else
50                     {
51                         dp[i+(1<<(j-1))][k+a[cnt+1][j]]+=dp[i][k];
52                     }
53                 } 
54             }
55         }
56         if(dp[(1<<n)-1][m]==0)
57             puts("No solution");
58         else
59         {
60             int g=gcd(f[n],dp[(1<<n)-1][m]);
61             printf("%d/%d\n",f[n]/g,dp[(1<<n)-1][m]/g);
62         }
63         
64         
65     }
66 }       

轉載于:https://www.cnblogs.com/1013star/p/10753272.html