Problem Arrangement (状压DP)-蒲公英云

Problem Arrangement (状压DP)

た入场券 2021-12-13 01:35 409阅读 0赞

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

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 }