题目链接：http://hihocoder.com/problemset/problem/1489?sid=1587434
Little Hi is playing a video game. Each time he accomplishes a quest in the game, Little Hi has a chance to get a legendary item.
At the beginning the probability is P%. Each time Little Hi accomplishes a quest without getting a legendary item, the probability will go up Q%. Since the probability is getting higher he will get a legendary item eventually.
After getting a legendary item the probability will be reset to ⌊P/(2I)⌋% (⌊x⌋ represents the largest integer no more than x) where I is the number of legendary items he already has. The probability will also go up Q% each time Little Hi accomplishes a quest until he gets another legendary item.
Now Little Hi wants to know the expected number of quests he has to accomplish to get N legendary items.
Assume P = 50, Q = 75 and N = 2, as the below figure shows the expected number of quests is
2*50%*25% + 3*50%*75%*100% + 3*50%*100%*25% + 4*50%*100%*75%*100% = 3.25
The first line contains three integers P, Q and N.
1 ≤ N ≤ 106, 0 ≤ P ≤ 100, 1 ≤ Q ≤ 100
Output the expected number of quests rounded to 2 decimal places.
50 75 2
3.25
参考题解https://blog.csdn.net/sinat_26253653/article/details/68937034?utm_source=blogxgwz1
https://blog.csdn.net/BuptZhengChaoJie/article/details/69831275?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param
坑的地方：
1）审题：每次未获得时，增加q，是在上次成功的概率p上增加q，所以是p+q，而不是1-p+q
2）dfs深搜模拟树的结构会超时
3）正确思路是，数学思想，获得两个物品（先获得物品1，在拿到1的基础上再获得物品2）的期望 = 先获得第一个物品的期望 + 获得第一个物品的基础上拿到物品2
的期望，参考题解第二个
4）在写代码时，谨慎使用double，注意p每次除以2取整数，所以可能提前为0了
AC代码，仅供参考：
#include<iostream> #include<vector> #include<bits/stdc++.h> using namespace std; int n,p,q; double result=0; int main() { cin>>p>>q>>n; double current_p = p/100.0; for(int i=1;i<=n;i++) { double accumulate_p = 1.0, sp = current_p; //sp = successful probability int count = 1; double e = 0; while(1) { e += count*accumulate_p* sp; if(sp>=1.0) break; accumulate_p *= (1-sp); sp += q/100.0; count++; if(sp>=1.0) sp = 1.0; } result +=e ; p = p/2; current_p = p/100.0; } printf("%.2f",result); return 0; }
原文：https://www.cnblogs.com/qiezi-online/p/13693859.html