[期望dp+记忆化搜索] light oj 1038 Race to 1 Again
来源：程序员人生 发布时间：2015-07-29 08:12:18 阅读次数：2363次
题意：
给1个数n，每次随机选它的1个约数去除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⑴/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⑻
#define inf ⑼99999999999999999LL
using 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⑴.0/cnt);
return dp[x]=ans;
}
int main()
{
int t,cas=1;
cin>>t;
memset(dp,⑴,sizeof(dp));
while(t--)
{
int n;
scanf("%d",&n);
printf("Case %d: %.7f
",cas++,dfs(n));
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
