本文共 1743 字，大约阅读时间需要 5 分钟。

定义$f[i][j]$表示区间$[i,j]$中的牌都摆放完成的最小期望次数

每次枚举一个端点$k$放在这里

设往左边倒的概率是$p_1$,往右边倒的概率是$p_2$,不倒的概率是$p_3$

$f[i][j]=p_1\ast (2\ast f[i][k-1]+f[k+1][j]+1)+p_2\ast (2\ast f[k+1][j]+f[i][k-1]+1)+p_3\ast (f[i][k-1]+f[k+1][j]+1)$

这么转移直接是$O(n^3)$爆炸

考虑每块骨牌都是一样的,直接定义$f[i]$表示连续放置$i$块相邻不倒的期望

那么考虑在位置$j$放上一个骨牌

这个骨牌不倒的期望次数是$\frac{1}{1-p_1-p_2}$

那么前面倒的期望是$\frac{1}{1-p_1-p_2}-1=\frac{p_1+p_2}{1-p_1-p_2}$

在倒的过程中,向左倒的概率是$\frac{p_1}{p_1+p_2}\ast \frac{p_1+p_2}{1-p_1-p_2}=\frac{p_1}{1-p_1-p_2}$

向右倒的期望次数是$\frac{p_2}{1-p_1-p_2}$

于是$f[i]=f[j-1]\ast \frac{1-p_2}{1-p_1-p_2}+f[i-j]\ast \frac{1-p_1}{1-p_1-p_2}+\frac{1}{1-p_1-p_2}$

$O(n^2)$递推即可

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 1009;double p1,p2,p3,f[maxn];const int inf = 1e9;int n;int main(){
   	while( cin >> n&&n )	{
   		for(int i=1;i<=n;i++)	f[i] = inf;		cin >> p1 >> p2;		double p3 = 1.0-p1-p2;		f[1] = 1.0/p3;		for(int i=2;i<=n;i++)		for(int j=1;j<=i;j++)			f[i] = min( f[i],f[j-1]*(1-p2)/p3+f[i-j]*(1-p1)/p3+1.0/p3 );		printf("%.2lf\n",f[n] );	}}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114876992 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！