[期望dp+记忆化搜索] light oj 1038 Race to 1 Again
发布时间：2020-12-13 20:45:58 所属栏目：PHP教程 来源：网络整理
导读：题意： 给1个数n，每次随机选它的1个约数去除n，直到除到1为止，问除的次数的期望。 思路： E[n]= E[n/a[1]]/cntE[n/a[2]]/cnt...E[n/a[n]]/cnt1 a[i]为n的约数，cnt为约数的个数。 明显a[i]=1 则(1⑴/cnt)E[n]=E[n/a[2]]/cnt...E[n/a[n]]/cnt1 记忆化搜索就
|
题意： 给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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |