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 }