zoj 3777 Problem Arrangement

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5264

题意：给出n道题目以及每一道题目不同时间做的兴趣值，让你求出所有做题顺序中兴趣值大于等于m的比例。用一个分数表示。

状压dp。枚举每一个状态，用二进制表示。dp[i][j]表示第i个题目，兴趣值为j的个数。

转移方程 dp[i|(1<<j)][k+a[num][j]]+=dp[i][k];兴趣值大于m的为 dp[1|(1<<j)][m]+=dp[i][k];

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define LL long long
 5 using namespace std;
 6 
 7 int t,n,m;
 8 int p[15][15];
 9 int dp[1<<13][1000];
10 int f[10000];
11 
12 LL gcd(LL a,LL b)
13 {
14     return b==0?a:gcd(b,a%b);
15 }
16 
17 int main()
18 {
19     scanf("%d",&t);
20     f[1]=1;
21     for(int i=2; i<=12; i++)
22     {
23         f[i]=f[i-1]*i;
24     }
25     while(t--)
26     {
27         scanf("%d%d",&n,&m);
28         memset(dp,0,sizeof(dp));
29         for(int i=0; i<n; i++)
30         {
31             for(int j=0; j<n; j++)
32             {
33                 scanf("%d",&p[i][j]);
34             }
35         }
36         dp[0][0]=1;
37         for(int i=0; i<=(1<<n); i++)
38         {
39             int num=0;
40             for(int j=0; j<n; j++)
41             {
42                 if(i&(1<<j)) num++;
43             }
44             for(int j=0; j<n; j++)
45             {
46                 if(i&(1<<j)) continue;
47                 for(int k=0; k<=m; k++)
48                 {
49                     if(k+p[num][j]>=m)
50                     {
51                         dp[i|(1<<j)][m]+=dp[i][k];
52                     }
53                     else
54                     {
55                         dp[i|(1<<j)][k+p[num][j]]+=dp[i][k];
56                     }
57                 }
58             }
59         }
60         if(dp[(1<<n)-1][m]==0)
61         {
62             printf("No solution
");
63         }
64         else
65         {
66             int g=gcd(f[n],dp[(1<<n)-1][m]);
67             printf("%d/%d
",f[n]/g,dp[(1<<n)-1][m]/g);
68         }
69     }
70     return 0;
71 }

View Code