B - Problem Arrangement ZOJ

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

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

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int dp[(<<)+][],a[][],cf2[],jc[];

 int main()

 {

     cf2[]=jc[]=;

     for(int i=;i<=;i++)

     {

         cf2[i]=cf2[i-]<<;

         jc[i]=jc[i-]*i;

     }

     int t,n,m;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<cf2[n];i++)

             for(int j=;j<=m;j++)

                 dp[i][j]=;

         for(int i=;i<n;i++)

             for(int j=;j<n;j++)

                 scanf("%d",&a[i][j]);

         dp[][]=;

         for(int i=;i<cf2[n];i++)

         {

             int num=;//num已经做了几道题

             for(int j=;j<n;j++)

                 if(i&cf2[j])

                     num++;

             for(int j=;j<n;j++)

                 if(!(i&cf2[j]))//如果第j题还没做

                 {

                     for(int k=;k<=m;k++)

                     {

                         int lim=min(m,k+a[j][num]);//多于m就算m，节省空间

                         dp[i|cf2[j]][lim]+=dp[i][k];

                     }

                 }

         }

         int ans1=jc[n],ans2=dp[cf2[n]-][m];

         if(ans2==)

             printf("No solution\n");

         else

         {

             int g=__gcd(ans1,ans2);

             printf("%d/%d\n",ans1/g,ans2/g);

         }

     }

     return ;

 }

状压呀

巴特西

B - Problem Arrangement ZOJ - 3777

最新文章

热门文章