uva 11762 Race to 1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【重做DP系列】 期望dp，记忆化搜索实现

题意：给一个数字n<=1（不一定是质数）,选小于等于n的质数，如果n能被该质数整除，就变为n = n/质数，如果不能整除，n保持不变。选了一个质数，能不能整除都算作一步。问n变为1，期望步数是多少

先设置几个量，tot表示小于等于n的质数个数，cnt表示这些质数里哪些能整除n,dp[n]表示n对应的期望步数

dp[n] = p0 dp[n] + p1 dp[x1] + p1 dp[x2] + …… + p1 dp[xm] + 1

P1表示选中某个质数可以整除n的概率，使得n变为xi，可知p1 = 1/tot，每个质数没选中的概率都是1/tot。中间部分容易理解，第1项表示选中一个质数不能被n整数，概率为p0，p0 = (tot-cnt)/tot = 1 - cnt/tot。后面+1是因为无论都付出一个步数

我们可以通过移向来变换公式

1
2
3
4
5
6
(1-p0) dp[n] = p1 * dp[x1] + p1 * dp[x2] + ....... + p1 * dp[xm] + 1
             = p1 * sum + 1
dp[n] = (p1 * sum + 1) / (1-p0)
      = (sum/tot + 1)  / (1 - (1 - cnt/tot))
      =  ((sum + tot)/tot) / (cnt/tot)
      = (sum + tot) / cnt

所以我们只需要预处理出tot和cnt就行了，其实不同预处理，只要筛好质数，保存下来就行了，详细见代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 1000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

bool isp[MAX+10],vis[MAX+10];
int prime[MAX+10],pnt;
double dp[MAX+10];

void init(){
	pnt = 0;
	cl(isp,true);
	for(int i = 2; i <= MAX; i++)
		if(isp[i]){
			prime[pnt++] = i;
			for(int j = i+i; j <= MAX; j += i)
				isp[j] = false;
		}
}

void dfs(int n){
	if(vis[n]) return ;
	vis[n] = true;
	int tot = 0 , cnt = 0;
	double sum = 0;
	while(tot < pnt && prime[tot] <= n){
		if(n % prime[tot] == 0){
			cnt++;
			dfs(n/prime[tot]);
			sum += dp[n/prime[tot]];
		}
		tot++;
	}
	dp[n] = (sum + (double)tot) / (double)cnt;
}

int main(){
	init();
	int cas,n;
	scanf("%d",&cas);
	cl(vis,false);
	vis[1] = true; dp[1] = 0.0;
	for(int c = 1; c <= cas; c++){
		scanf("%d",&n);
		dfs(n);
		printf("Case %d: %.10lf\n",c,dp[n]);
	}
	return 0;
}