hdu 6558 The Moon（概率dp）

ゝ一世哀愁。 2021-11-16 15:24 285阅读 0赞

## 题意：每赢一局 (赢的概率为 p) 能以概率 q 开一个箱子，如果开箱失败 q = q + 2%，如果该局失败 q = q + 1.5%。求直到成功开箱之前期望。 ##

## 分析：已知的状态很明显，当获胜中奖概率为100%，这个时候期望是已知的就是1/p，例如一个硬币抛起来正反面的概率都是1/2。得到正面或者反面，期望的次数就是2。定义状态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\]。如果掉落率已经100%了，即q==200，那么ans=100/p；否则，ans=1（本场游戏）+获胜并且没掉落物品的情况+没获胜的情况 （如果获胜并且掉落物品的话，游戏就结束了，就没有后继情况了） ##

## 1.获胜并且没掉落物品 ##

## 概率：p/100 \* （1-q/1000） ##

## 后继状态：dp\[min(1000,q+20)\] ##

## 产生的贡献：dp\[i\]=p/100\*(1-q/1000)\*dp\[min(1000,q+20)\] ##

## 2.没获胜 ##

## 概率：1- p/100  ##

## 后继状态：dp\[min(1000,q+15)\] ##

## 所以产生的贡献：(1-p/100)\*dp\[min(1000,q+15)\] ##

## 参考：[https://blog.csdn.net/aiyouyou\_/article/details/89788586][https_blog.csdn.net_aiyouyou_article_details_89788586]。 ##

## 总结：**一般求概率是正推，求期望是逆推。通过特殊的边界条件找到递推入口，通过所求设计状态和转移方程。** ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    double dp[1100];
    int p;
    double dfs(int q) {
        if (dp[q] != -1)
            return dp[q];
        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;
        return dp[q];
    }
    int main() {
        int t, cas = 1;
        scanf("%d", &t);
        while (t--) {
            scanf("%d", &p);
            for (int i = 0; i <= 1000; i++) dp[i] = -1;
            dp[1000] = 100.0 / (p*1.0);
            printf("Case %d: %.6f\n", cas++, dfs(20));
        }
    }

[https_blog.csdn.net_aiyouyou_article_details_89788586]: https://blog.csdn.net/aiyouyou_/article/details/89788586