HDU 4336 容斥原理 || 状压DP

时间：2022-11-10 19:29:47

状压DP :F(S)=Sum*F(S)+p(x1)*F(S^(1<<x1))+p(x2)*F(S^(1<<x2))...+1;

F(S)表示取状态为S的牌的期望次数，Sum表示什么都不取得概率，p(x1)表示的是取x1的概率，最后要加一因为有又多拿了一次.整理一下就可以了。

 #include <cstdio>

 const int Maxn=;

 double F[<<Maxn],p[Maxn];

 int n;

 int main()

 {

     while (scanf("%d",&n)!=EOF)

     {

         double Sum=;

         for (int i=;i<=n;i++) scanf("%lf",&p[i]),Sum+=p[i];

         F[]=; Sum=-Sum; //Sum表示为空的概率. 状态位为1表示该张卡片还未取.

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

         {

             double X=,Ret=;

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

             {

                 if (!(i&(<<(j-)))) X+=p[j];

                 else Ret+=p[j]*F[i^(<<(j-))];

             }

             X=X+Sum;

             F[i]=(Ret+)/(-X);

         }

         printf("%.5lf\n",F[(<<n)-]);

     }

     return ;

 }

状压DP

容斥原理： 若发生的概率为p，第一次发生的概率的期望是1/p，我感觉并不是很显然。

Prove：E=p+p(1-p)*2+p*(1-p)^2*3+...=pS

　　　　S=1+(1-p)*2+(1-p)^3..=1/p^2

　　　　∴Ep=1

　　那么两个发生的期望就为1/(p1+p2)

　　三个发生的期望为1/(p1+p2+p3)

 #include <cstdio>

 const int Maxn=;

 double F[<<Maxn],p[Maxn];

 int n;

 int main()

 {

     while (scanf("%d",&n)!=EOF)

     {

         double Ans=;

         for (int i=;i<=n;i++) scanf("%lf",&p[i]);

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

         {

             double Sum=; int cnt=;

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

                 if (i&(<<(j-)))

                 {

                     Sum+=p[j];

                     cnt++;

                 }

             if (cnt&) Ans+=/Sum; else Ans-=/Sum;

         }

         printf("%.5lf\n",Ans);

     }

     return ;

 }

容斥原理

相关文章