[期望dp+記憶化搜索] light oj 1038 Race to 1 Again
來源：程序員人生 發布時間：2015-07-29 08:12:18 閱讀次數：2506次
題意：
給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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
