[UVA 10529]Dumb Bones

时间：2023-03-08 16:18:32

题面在这里

题意

放\(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<bits/stdc++.h>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<complex>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define mp make_pair

#define pb push_back

#define RG register

#define il inline

using namespace std;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

const dd eps=1e-10;

const int inf=2147483647;

const int mod=1e9+7;

const int N=5010;

const int M=50010*2;

il ll read(){

	RG ll data=0,w=1;RG char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

	return data*w;

}

il void file(){

	//freopen("a.in","r",stdin);

	//freopen("a.out","w",stdout);

}

int n;

dd f[N],pl,pr;

il void DP(){

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

		f[i]=inf;

		for(RG int j=0;j<=i;j++)

			f[i]=min(f[i],f[j]*(1-pl)/(1-pl-pr)+f[i-j-1]*(1-pr)/(1-pl-pr)+1/(1-pl-pr));

	}

}

int main()

{

	while(n=read()){

		scanf("%lf%lf",&pl,&pr);

		DP();printf("%.2lf\n",f[n]);

	}

	return 0;

}

相关文章