概率dp专题整理(2/2)

LightOJ 1027 A Dangerous Maze:

预先求出递推式,最后通过公式直接计算。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int gcd(int a, int b){
	if (b == 0)
		return a;
	return gcd(b, a%b);
}
int main(){
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++){
		int n;
		scanf("%d", &n);
		int p = 0, q = n,num;
		for (int i = 1; i <= n; i++){
			scanf("%d", &num);
			if (num < 0){
				q--;
				p -= num;
			}
			else{
				p += num;
			}
		}
		if (q == 0){
			printf("Case %d: infn",t);
		}
		else{
			int div = gcd(p, q);
			printf("Case %d: %d/%dn",t,p/div,q/div);
		}
	}
}

LightOJ 1284 Lights inside 3D Grid:

要判断经过k次变换后的开灯的数目,我们可以先计算对于每一个cell而言,在经历了k次变换后,仍然开灯的期望,最后将每一个cell的期望相加即可。

有一个M*N*P的立方体,每次随机选两个格子,把它们之间的灯全打开(如果已经是打开的就关闭),经过K次操作之后开着的灯的个数的期望是多少。

把每个灯经过K次操作亮着的概率P求出来,因为每个灯是独立的,最后的期望也就是:
$$\Sigma(Pi*1+(1-Pi)*0)$$

对于一个灯来说, 设f[i]是经过i次操作亮着的概率,g[i]是经过i次操作不亮的概率,则有$f[i]+p[i]=1,f[i]=f[i-1]*(1-p)+g[i-1]*p$,这里的p是操作一次能操作到这个灯的概率。

通过这两个式子,能得到$f[i]=f[i-1]*(1-2p)+p$,两边加上b/(a-1),也就是0.5,成为等比数列,最后得到$f[i]=0.5-0.5*(1-2p)^i$。

那么只要对每个灯求出p就能算出答案了。能操作到这个灯等价于选的两个点的坐标在x轴,y轴,z轴都分别在这个灯坐标的两侧,对每个轴分别算符合的情况,然后相乘,最后除以所有情况就是概率。

#include <cstdio>
#include <cmath>

double Get (int a,int b)
{
    return 1.0*b*b-(a-1)*(a-1)-(b-a)*(b-a);
}

int main ()
{
	int T;
	scanf("%d",&T);
	for (int Cas=1;Cas<=T;Cas++)
	{
		int x,y,z,n;
		scanf("%d%d%d%d",&x,&y,&z,&n);
		double ans=0,p,t=1.0*x*x*y*y*z*z;
		for (int i=1;i<=x;i++) 
			for (int j=1;j<=y;j++)
				for (int k=1;k<=z;k++)
				{
					p=1.0*Get(i,x)*Get(j,y)*Get(k,z)/t;
					ans+=0.5-0.5*pow(1-2*p,1.0*n);
				}
		printf("Case %d: %lfn",Cas,ans);
	}
	return 0;
}