当前位置：首页 -> 基础 -> c++编程基础

动态规划晋级――Race to 1 Again

2014-11-23 23:40:16 · 作者: · 浏览: 3
标签: 动态 规划 晋级 Race Again
分析：
题意：给一个数，用这个数的约数(包括自己)去除这个数，直到得数为1，求除的次数的期望。
思路：设一个数的约数有num个，E[n] = E[a[1]]/num+E[a[2]]/num+...+E[a[num]]/num+1 (因为又除一次，所以+1)
整理得：E[n]=(E[a[1]]+E[a[2]]+...+E[a[num-1]]+num)/(num-1) 
#include  
#include  
const int N=100010;  
double dp[N];  
void Init (){  
    dp[1]=0;  
    for (__int64 i=2;i