[期望dp+记忆化搜索] light oj 1038 Race to 1 Again

题意：

给一个数n，每次随机选它的一个约数去除n，，直到除到1为止，问除的次数的期望。

思路：

E[n]= E[n/a[1]]/cnt+E[n/a[2]]/cnt+…+E[n/a[n]]/cnt+1

a[i]为n的约数，cnt为约数的个数。

显然a[i]=1 则(1-1/cnt)E[n]=E[n/a[2]]/cnt+…+E[n/a[n]]/cnt+1

记忆化搜索就ok了~

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#include"stack"#include"vector"#define ll __int64#define eps 1e-8#define inf -999999999999999999LLusing namespace std;double dp[123567];double dfs(int x){if(x==1) return 0.0;if(fabs(dp[x]+1)>eps) return dp[x];int cnt=0;double ans=1.0;int lit=sqrt(x*1.0);for(int i=1; i<=lit; i++) //统计因子数{if(x%i==0){if(i*i==x) cnt++;else cnt+=2;}}for(int i=1; i<=lit; i++) //求期望的和{if(x%i==0){if(i*i==x) ans+=1.0/cnt*dfs(x/i);else{if(i!=1) ans+=1.0/cnt*dfs(x/i);ans+=1.0/cnt*dfs(i);}}}ans=ans/(1-1.0/cnt);return dp[x]=ans;}int main(){int t,cas=1;cin>>t;memset(dp,-1,sizeof(dp));while(t–){int n;scanf("%d",&n);printf("Case %d: %.7f\n",cas++,dfs(n));}return 0;}

使用双手头脑与心灵的是艺术家，只有合作双手