HDU - 6558/概率dp（从后往前推导）

VJ地址
中文题意：
有一个苦逼程序员小A，他有一个女朋友B，最近看上了一个游戏，他想买这个游戏，可是小A是一个怕老婆的人，每个 月的工资都需要上交，小A找他女朋友商量了好久，最后B同意他用每个月的工作奖金来买游戏，且还需要和B玩智力游戏，赢了才能去买游戏，具体情况是这样的：
步骤1. 先假设小A 赢 小B的几率为 q = 2%
步骤2. 这个月小 A 获得工作奖金的几率为 P
步骤3. 如果这个月小 A 获得了工作奖金则转到步骤 4，否则转到步骤5
步骤4. 如果小 A 以 q 的胜率赢了小B，小A就可以去买游戏了，如果没有赢，则 q = min（100％， q+ 2％）,并转到步骤2
步骤5. 小A 不甘心，使得 q = min(100%,q+1.5%),并转到步骤2进行下一个月
那么请问，当你知道小 A 获得奖金几率为 p 的情况下，小 A 预期要用几个月才能买到自己的游戏（即求 月数 的期望）

思路：
概率dp
dp[i]表示在q的概率等于i的时候，A预计要dp[i]个月才能获胜（既数学期望），那么当i=100时，dp[i]=1/p;
当小于100时，
因为1.5是小数，不能当下标，所以2，翻倍处理
dp[i]=qi1.0/200.0(赢了)+q(1-i1.0/200.0)(dp[min(i+4,200)]+1)（得了工作奖金但是输给B）+(1-q)*(dp[min(i+3,200)]+1)（没有得到工作奖金）;

代码：

#include <bits/stdc++.h> #define lc u << 1 #define rc u << 1 | 1 using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int N = 4e6+10; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9+7; const double eps = 1e-8;double dp[210]; int cc; void solve() {double q;cin>>q;q/=100;dp[200]=1/q;for(int i=199;i>=4;i--){dp[i]=q*i*1.0/200.0+q*(1-i*1.0/200.0)*(dp[min(i+4,200)]+1)+(1-q)*(dp[min(i+3,200)]+1);}printf("Case %d: %.9f\n",++cc,dp[4]); } int main() {int t;t=1;cin>>t;while(t--){solve();}return 0; }

总结

以上是生活随笔为你收集整理的HDU - 6558/概率dp（从后往前推导）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。