题目链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=867
当时年少不懂期望dp，时隔一年看到这道题感觉好容易....
定义状态dp[i]表示当前的q值为i时的期望，则当q值为100时dp[100]=100/q，这时后发现转移过程中有1.5这种小数出现，则把空间变为1000,q值也相应扩大10倍。
则转移方程为dp[i]=p/100*(1-q/1000)*dp[min(1000,q+20)]+(1-p/100)*dp[min(1000,q+15)]+1。
最后的答案为dp[20]。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 double dp[1100]; 5 int p; 6 double dfs(int q) { 7 if (dp[q] != -1) 8 return dp[q]; 9 dp[q] = (1.0*p / 100.0)*(1 - 1.0*q / 1000.0) * dfs(min(1000, q + 20)) + (1 - 1.0*p / 100.0)*dfs(min(1000, q + 15)) + 1.0; 10 return dp[q]; 11 } 12 int main() { 13 int t, cnt = 1; 14 scanf("%d", &t); 15 while (t--) { 16 scanf("%d", &p); 17 for (int i = 0; i <= 1000; i++) 18 dp[i] = -1; 19 dp[1000] = 100.0 / (p*1.0); 20 printf("Case %d: %.6f\n", cnt++, dfs(20)); 21 } 22 }
原文：https://www.cnblogs.com/sainsist/p/11194499.html