hdu 4870 Rating

　　题目链接：hdu 4870

　　这题应该算是概率 dp 吧，刚开始看了好几个博客都一头雾水，总有些细节理不清楚，后来看了 hdu 4870 Rating (概率dp) 这篇博客终于有如醍醐灌顶，就好像是第 7 个烧饼一样，终于感到饱了。

　　还是适当贴下图先：

　　按照这个思路我的代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 double dp[23];
 7 
 8 int main() {
 9     double p;
10     while(~scanf("%lf",&p)) {
11         dp[0] = 1 / p;
12         dp[1] = 1 + (1 - p) / p * (1 + dp[0]);
13         double sum = dp[0] + dp[1];
14         for(int i = 2; i <= 19; ++i) {
15             dp[i] = 1 + (1 - p) / p * (dp[i - 2] + dp[i - 1] + 1);
16             sum += dp[i];
17         }
18         printf("%.6f
",sum * 2 - dp[19]);
19     }
20     return 0;
21 }