B - Problem Arrangement ZOJ - 3777

Problem Arrangement ZOJ - 3777 

  题目大意:有n道题,第i道题第j个做可以获得Pij的兴趣值,问至少得到m兴趣值的数学期望是多少,如果没有的话就输出No solution。

  数学期望很好求,求出符合的方案数与总方案之比就是概率,概率的倒数就是期望。问题在于怎么安排这些题目的做题顺序,如果直接暴力的话,有12!种情况,铁定超时,所以我们可以转换成dp的思想,总共就是12道题,也就212-1种状态,我们枚举每个状态得多少分时的方案数,最终符合的方案数就是dp[212-1][m]。然而重点在于怎么表示这个状态,以及转移。我想的是二进制对应的第i位是0或者1就代表第i个题安排了没有,但是这样的话转移的时候就是要4重循环,果断超时。而观摩了qxdywjy的代码后,状态表示是二进制对应的第i位是0或者1就代表第i道题做了,这样状态的转移就只有用三重循环了,转移就是遍历所有状态,状态i如果第j题没做,那么转移到i|(1<<j)状态中,它就是是第num个做,num就是已经做了多少道题。

B - Problem Arrangement ZOJ - 3777
 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int dp[(1<<12)+10][520],a[15][15],cf2[15],jc[15];
 5 int main()
 6 {
 7     cf2[0]=jc[0]=1;
 8     for(int i=1;i<=12;i++)
 9     {
10         cf2[i]=cf2[i-1]<<1;
11         jc[i]=jc[i-1]*i;
12     }
13     int t,n,m;
14     scanf("%d",&t);
15     while(t--)
16     {
17         scanf("%d%d",&n,&m);
18         for(int i=0;i<cf2[n];i++)
19             for(int j=0;j<=m;j++)
20                 dp[i][j]=0;
21         for(int i=0;i<n;i++)
22             for(int j=0;j<n;j++)
23                 scanf("%d",&a[i][j]);
24         dp[0][0]=1;
25         for(int i=0;i<cf2[n];i++)
26         {
27             int num=0;//num已经做了几道题 
28             for(int j=0;j<n;j++)
29                 if(i&cf2[j])
30                     num++;
31             for(int j=0;j<n;j++)
32                 if(!(i&cf2[j]))//如果第j题还没做 
33                 {
34                     for(int k=0;k<=m;k++)
35                     {
36                         int lim=min(m,k+a[j][num]);//多于m就算m,节省空间 
37                         dp[i|cf2[j]][lim]+=dp[i][k];
38                     }
39                 }
40         }
41         int ans1=jc[n],ans2=dp[cf2[n]-1][m];
42         if(ans2==0)
43             printf("No solution\n");
44         else
45         {
46             int g=__gcd(ans1,ans2);
47             printf("%d/%d\n",ans1/g,ans2/g);
48         }
49     }
50     return 0;
51 } 
状压呀

 

上一篇:ARE 212: Problem Set 3


下一篇:LVS三种模式分析(超详细)