20190716-T1-礼物

呵呵，我暴力WA了

这个题充分考验了大家对数学的理解（麦蒙大多在胡诌）

但是确实如此啊。

看数据范围想状压。（我额嗯嗯想到暴力？）

然后设出一个可爱的$dp$式（主语当然不是我，是出题人大佬）

$f_s$表示二进制组昂态（状态）为$s$时的期望。

那么我们可以从$s'$转移过来，其中$s' or\ s = s$或$s' and\ s =s$（$and$和$or$均为位运算）（内两个式子是等效的）

那么有：

$f_s= \sum\limits_{i=1}^N p_i \times f_{s'}+(1-\sum \limits_{i=1}^N p_i) \times f_s +1$

真是恐怖，$f_s$转移需要自己～

但是表慌，数学老师可以拯救你，哒哒哒

移项。式子变为：

$\begin{array}{lcl}0 & = & \sum \limits_{i=1}^N p_i \times f_{s'}-f_s \times \sum \limits_{i=1}^N p_i +1\\f_s & = & \frac{\sum \limits_{i=1}^N p_i \times f_{s'}+1}{\sum \limits_{i=1}^N p_i}\end{array}$

还是比较简单的。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 //#include "debug.h"

 #define N 22

 using namespace std;

 int n;

 double p[N];

 long long val,dat;

 double dp[(<<)+];

 int main(){

     scanf("%d",&n);

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

         scanf("%lf%lld",&p[i],&dat);

         val=val+dat;

     }

     cout<<val<<endl;

     double ons=,sums=;

     for (int s=;s<<<n;s++){

         ons=sums=;

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

             if (s&(<<(i-))){

                 ons+=dp[s^(<<(i-))]*p[i];//cout<<bin(s,n)<<"<<"<<bin(s^(1<<(i-1)),n)<<endl;

                 sums+=p[i];//cout<<sums<<endl;

             }

         }//cout<<"O:"<<ons<<"  S:"<<sums<<endl;

         if(sums==){

     //        cout<<"T0T"<<NL;

             continue;

         }

         dp[s]=(ons+1.0)/sums;

     }

 //    pour(dp,1,1<<n,10,"Dp");

     printf("%.3lf\n",dp[(<<n)-]);

     return ;

 }

巴特西

20190716-T1-礼物

最新文章

热门文章