2018CCPC吉林赛区（重现赛）D. The Moon（期望dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6558

解题心得：

首先这是个没有止境的游戏，但是在某一个状态答案是已知的，然后从这个已知的答案，往回推可以得到最终的结果。就这个题来说已知的状态很明显，就是最后只要获胜中奖概率为$100\%$，这个时候期望是已知的就是$1/p$，为啥，例如一个硬币抛起来正反面的概率都是$1/2$，你想要得到正面，期望的次数就是$2$。然后这个题转移状态就比较简单了，只是有两个状态可能稍微有些绕，但是可以直接写记忆化，这样思维比较清晰，当然对大佬来说直接推$DP$方程也很简单。还要注意一下因为有个$1.5\%$，这里可以用$200$为最终态。$DP[i]$为中奖几率为$i$时期望的游戏轮数。

---

记忆化代码

#include <bits/stdc++.h> using namespace std; const int maxn = 500; double dp[maxn]; int p; double P; double dfs(int q) { if(q > 200) q = 200; double Q = double(q)/200; if(q == 200) return dp[q] = double(100)/p; if(dp[q] > -1) return dp[q]; return dp[q] = double(1) + P * (1-Q)* dfs(q+4) + (1-P)*dfs(q+3);//当前未中奖多一次以及未中奖的所有可能 } int main() { // freopen("1.in.txt", "r", stdin); int t; scanf("%d", &t); int T = t; while(t--) { for(int i=0;i<maxn;i++) dp[i] = -1; scanf("%d", &p); P = double(p)/100; printf("Case %d: %.10f\n",T-t, dfs(4)); } return 0; }

DP代码：

#include <bits/stdc++.h> using namespace std; const int maxn = 500; double dp[maxn]; int p; int main() { // freopen("1.in.txt", "r", stdin); int t; scanf("%d", &t); int T = t; while(t--) { for(int i=0;i<maxn;i++) dp[i] = 0.0; scanf("%d", &p); double P = double(p)/100.0; dp[200] = double(1)/P; for(int i=199;i>=0;i--) { double Q = double(i)/200; dp[i] = P*(Q + (1.0-Q)*(1.0+dp[min(200, i+4)])); dp[i] += (1.0-P) * (1.0 + dp[min(200, i+3)]); } printf("Case %d: %.10f\n",T-t, dp[4]); } return 0; }