动态规划晋级——Race to 一 Again【概率DP】

动态规划晋级——Race to 1 Again【概率DP】

转载请注明出处：http://blog.csdn.net/a1dark

分析：

题意：给一个数，用这个数的约数(包括自己)去除这个数，直到得数为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<stdio.h>
#include<cmath>
const int N=100010;
double dp[N];
void Init (){
	dp[1]=0;
	for (__int64 i=2;i<N;i++){
		double sum=0;
		int cnt=0;
		for (__int64 j=1;j*j<=i;j++)//这里必须要优化、否则会超时
			if (i%j==0){
				sum+=dp[j];
				cnt++;
				if(j*j!=i){
                    sum+=dp[i/j];
                    cnt++;
				}
			}
		sum+=cnt;
		dp[i]=sum/(cnt-1);
	}
}
int main (){
	int T,n;
	scanf("%d",&T);
	Init ();
	for (int Cas=1;Cas<=T;Cas++){
		scanf("%d",&n);
		printf("Case %d: %lf\n",Cas,dp[n]);
	}
	return 0;
}