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

Posted on | In

LightOJ 1027 A Dangerous Maze:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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轴都分别在这个灯坐标的两侧，对每个轴分别算符合的情况，然后相乘，最后除以所有情况就是概率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}