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;
}