Luogu_3239 [HNOI2015]亚瑟王

vim-markdown 真好用

这个题难了我一下午

第一道概率正而八经\(DP\)，还是通过qbxt讲解才会做的。

发现真是个dalao。讲的真是很清楚。代码也比较干净

做题心得:

1.概率和期望联系紧密。若无法直接计算期望，可是用期望的性质，将问题转化为算概率

2.若目标概率无法直接计算，可以通过计算过程中的某个步骤的概率，间接的计算出目标概率

若跟据局面进行状压\(DP\),时间复杂度成熟不起。

考虑优化状态。

发现，对于某一张牌，我们只要知道他用没有用过就行了。

所以一个很重要的操作就是定序。

我们只需要枚举某一张牌。在某一个局面中是否会被选中就可以了。

根据某一个局面出现的概率，便可计算出某一张牌在某个局面被选的概率，从而推出期望。

那么问题就是推出这个局面出现的概率。也就是过程中某个步骤的概率。

我们可以更改一下决策， 我们只需要枚举在某一个局面中。要么在剩余j轮(也就是当前局面)的时候被选中，要么在永远不会被选中

然后直接转移到决策下一张卡。

这样做， 我们可以避免同一张卡之间不同决策之间的互相影响， 又可以不丢失任何答案。

---

设\(f_{i,j}\)为前\(i\)张卡牌已经决策完了，还剩下\(j\)局可以进行

根据上面的说明，便可以写出状态转移方程

\(f_{i,j}=f_{i-1,j}*(1-p_i)^j+f_{i-1,j+1}*(1-(1-p_i)^{j+1})\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using std::bitset;const int maxn=101000;const int MAX=100000;const long long mod=1000000001;const int log_2=17;const int log_3=11;int n;long long map[log_2][300];int check[log_2][log_3];int Log_2,Log_3;int len[log_2];int step[maxn],tot;bitset
          
           vis;void init(){ for(int i=0;i<(1<