首页 > 代码库 > HDU 4465 递推与double的精确性
HDU 4465 递推与double的精确性
题目大意不多说了
这里用dp[i][0] 代表取完第一个盒子后第二个盒子剩 i 个的概率，对应期望就是dp[i][0] *i
dp[i][1] 就代表取完第二个盒子后第一个盒子剩 i 个的概率
dp[i][0] = p^(n+1) * (1-p)^(n-i) * C(2*n-i , n-i) = p^(n+1) * (1-p)^(n-i) * (2*n-i)！ / (n-i)！ / n！
dp[i+1][0] = p^(n+1) * (1-p)^(n-i-1) * C(2*n-i-1 , n-i-1) = p^(n+1) * (1-p)^(n-i-1) * (2*n-i-1)！ / (n-i-1)！ / n！
dp[i][0] = dp[i+1][0] * (1-p) * (2*n-i) / (n-i)
dp[i][1]也是一样的道理
如果一开始给dp[n][0] 赋初值 pow(p,n+1) 那么如果n过大，那么因为精确度问题得到的是0
所以n+1个p在计算过程中在答案超过总数时一个一个往里乘
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 using namespace std; 5 const int N = 200005; 6 double dp[N][2]; 7 8 int main() 9 {10 // freopen("test.in","rb",stdin);11 12 int n,cas = 0;13 double p;14 while(scanf("%d%lf",&n,&p)!=EOF){15 double ans1 = 0;16 double ans2 = 0;17 int last[2];18 last[0] = last[1] = n+1;19 double q = 1-p;20 dp[n][0] = 1;21 dp[n][1] = 1;22 ans1 += n;23 ans2 += n;24 for(int i=n-1;i>=1;i--){25 double tmp1 = q * (2*n-i) / (n-i);26 double tmp2 = p * (2*n-i) / (n-i);27 28 //递推过程，因为数目太多，p直接开方，数据大点的话就直接因精确度不够变为029 //所以每次在答案超过总数的情况下乘个p值30 dp[i][0] = tmp1 * dp[i+1][0];31 dp[i][1] = tmp2 * dp[i+1][1];32 ans1 += (dp[i][0] * i);33 while(ans1>n){34 dp[i][0] *= p;35 ans1 *= p;36 last[0]--;37 }38 ans2 += (dp[i][1] * i);39 while(ans2>n){40 dp[i][1]*=q;41 ans2 *= q;42 last[1]--;43 }44 }45 // cout<<" dp "<<dp[n]<<endl;46 ans1 *= pow(p,last[0]);47 ans2 *= pow(q,last[1]);48 cas++;49 50 printf("Case %d: %.6f\n",cas,ans1+ans2);51 }52 return 0;53 }
HDU 4465 递推与double的精确性
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。