链接：https://vjudge.net/contest/400607#problem/D
突然想起来概率里面还有一个概率dp，这个之前确实学的不扎实，通过这道题回顾一下。
题意：打一局游戏的胜率是p，初始开箱爆率是q=2%，每打一局游戏如果赢了，可以开箱，如果没开中，开箱爆率会加2%（最大为100%）。如果游戏输了，开箱爆率为加1.5%，求开中箱需要玩多少局游戏的期望。
解法：
这是一道期望dp，期望dp一般来讲是逆推
设dp[p][q]为胜率为p，开箱率为q的局数的期望。
注：因为dp的下标都是整数，会出现1.5这种的话，我们让q为1000
考虑一下状态转移方程：
dp[p][q] = 1.0 + dp[p][q+15](1-p) + dp[p][q+20]*p(1-q)
理解为这一局+后面的期望局数
最终状态dp[p][1000]表示胜率为p，开箱率为100%的局数的期望，也就是一个伯努利实验，那么伯努利实验的结论是期望=概率的倒数，也就是说dp[p][1000]=1.0/p
实现方式，记忆化搜索更方便一些。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1010;
double dp[110][maxn];

double dfs(int p, int q) {
    if(q >= 1000) return 100.0/p;
    if(dp[p][q] != -1) return dp[p][q];
    dp[p][q] = 1.0 + dfs(p, q + 15) * (1.0 - p/100.0) + dfs(p, q + 20) * (p/100.0) * (1.0 - q/1000.0);
    return dp[p][q];
}

int main()
{
    int t, p, cnt = 0;
    scanf("%d",&t);
    for(int i = 0; i < 110; i++) {
        for(int j = 0; j < maxn; j++) {
            dp[i][j] = -1;
        }
    }
    while(t--)
    {
        scanf("%d",&p);
        printf("Case %d: %.6lf\n", ++cnt ,dfs(p, 20));
    }
    return 0;
}