题面在

题意

放\(n\)个相连的骨牌,每次放的时候有\(pl\)的概率往左倒,有\(pr\)的概率往右倒,骨牌倒的时候可能会打翻左边相邻或者右边相邻的骨牌,并引起连锁反应直到最后一个骨牌旁边没有与之相邻的骨牌为止

例如\(DD\) _ \(DxDD\) _ \(DD\),

如果在\(x\)处放置骨牌,有可能会让左边的一个或者右边的两个一起倒

求期望放置骨牌的次数

\(T\le100,n\le1000,0<pl+pr\le0.5\)

sol

别人家的题解完全看不懂啊...还是自己写一篇吧

首先考虑单独摆一张骨牌成功的期望次数,记作\(E\)

只要往左倒或者往右倒就要重新摆放,即

\[E=1+pl\times(1+pl\times(...)+pr\times(...))+pr\times(1+pl\times(...)+pr\times(...))\]

\[=1+(pl+pr)\times(1+(pl+pr)\times(1+(pl+pr)\times(...)))\]

\[=1+(pl+pr)+(pl+pr)^2+(pl+pr)^3+...+(pl+pr)^{\infty}\]

\[=\frac{1}{1-pl-pr}\]

这个式子总算化完了.

如果几张骨牌一起放呢?最优策略又是什么?

考虑放最后一张骨牌的时候,肯定只会剩下一个空位。

那么我们分别把左边和右边的骨牌按照最优策略摆好,再把中间的骨牌摆上去就可以了。

而这个位置可以通过枚举得到......

于是设\(f[x]\)表示摆好连续的\(x\)张骨牌的期望步数,那么

\[f[x]=min_{i=0}^{x}{(1+f[i]+f[x-i-1]+[在第(i+1)个位置摆好这张骨牌的期望步数])}\]

我们把[在第i个位置摆好这张骨牌的期望步数]记作\(g[i]\)

直接求\(g[i]\)难以统计,我们考虑算出每一部分(左边i-1块/中间一块/右边x-i块)的贡献

左边i-1块:

中间的骨牌每次往左倒,左边i-1块都需要重摆,

于是答案为\(f[i-1]\times[骨牌往左倒的期望次数]\),这里

\[[骨牌往左倒的期望次数]=(E-1)\frac{pl}{pl+pr}=\frac{1-pr}{1-pl-pr}\]

(\(E=\frac{1}{1-pl-pr}\))

(考虑骨牌每次倒地,有\(\frac{pl}{pl+pr}\)的概率往左倒,有\(\frac{pr}{pl+pr}\)的概率往右倒)

中间一块:

上面已经求出,为\(\frac{1}{1-pl-pr}\)

右边x-i块:

同左边i-1块的求法,为\(f[x-i]\times\frac{1-pl}{1-pl-pr}\)

于是\[g[i]=f[i-1]\times\frac{1-pr}{1-pl-pr}+\frac{1}{1-pl-pr}+f[x-i]\times\frac{1-pl}{1-pl-pr}\]

那么就可以求解了~

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include