本文主要是介绍【HDU】 4089 Activation 概率DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：Tomato要玩一个游戏，他需要排队，一开始这个队列共有N个人，而他在队列的第M个位置，每当有玩家尝试激活登陆游戏时， 会概率性触发四个事件。p1的概率注册失败，队列无变化。p2的概率连接失败，排在队首的人排到队尾。p3的概率成功，队首出队。p4的概率服务器 瘫痪，停止激活！这时候如果排在Tomato前面的人不足K个，那么他会很气愤。问 : Tomato排在第k位以内服务器瘫痪的概率。
令dp[i][j]为一共有i个人的队列Tomato排在第j位服务器瘫痪的概率，通过采用逆推，那么我们可以得到一组状态转移方程：
i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1][1] * p2 + p4;
i > 1 :
2 <= j <= k : dp[i][j] = dp[i][j] * p1 + dp[i][j - 1] * p2 + dp[i - 1][j - 1] * p3 + p4;//前面不足K个人，Tomato愤怒
k + 1 <= j <= i : dp[i][j] = dp[i][j] * p1 + dp[i][j - 1] * p2 + dp[i - 1][j - 1] * p3;
（这里k可能大于i，我们暂且不管，在下面我们再来消去这里的副作用）
令pp = p2 / (1 - p1) , pp3 = p3 / (1 - p1) , pp4 = p4 / (1 - p1);
令：
i == 1 c[1] = pp4;
2 <= j <= k : c[j] = dp[i - 1][j - 1] * pp3 + pp4;
k + 1 <= j <= i : c[j] = dp[i - 1][j - 1] * pp3;
消去k>i的情况：1 <= j <= i : c[j] = dp[i - 1][j - 1] * pp3 + (j <= k ? pp4 : 0);（这里我们默认dp[0][j]已经初始化）
进而化简得到:
j == 1 : dp[i][1] = dp[i][i] * p + c[1]; (1)
2 <= j <= i : dp[i][j] = dp[i][j - 1] * pp2 + c[j];
由递推关系可知 :dp[i][i] = dp[i][1] * p ^ (i - 1) + tmp; (2)
其中tmp = c[1] ^ (i - 1) + c[2] ^ (i - 2) + ... + c[i - 1];
联立(1)、(2) 消去dp[i][1]得 : dp[i][i] = tmp / (1 - p ^ i); （也可以消去dp[i][i]）
回代得原式 :2 <= j < i: dp[i][j] = dp[i][j - 1] * p + c[j];
最终解即为dp[n][m]。
代码如下：
//HDU 4089 Activation 概率DP
/*p = p2 / (1 - p1)p31 = p3 / (1 - p1)p41 = p4 / (1 - p1)i = 1: c[1] = pp4, dp[1][1] = pp4 / (1 - p)j == 1:c[1] = pp4;2 <= j <= k:c[j] = dp[i - 1][j - 1] * pp3 + pp4;(1)k + 1 <= j <= i:c[j] = dp[i - 1][j - 1] * pp3; (2)联立(1)、(2) 得:2 <= j <= i: c[j] = dp[i - 1][j - 1] * pp3 + (i <= k ? pp4 : 0);易知:j == 1:dp[i][1] = dp[i][i] * p + c[1]; (3)2 <= j <= k:dp[i][j] = dp[i][j - 1] * p + c[j]; (4)k + 1 <= j <= i:dp[i][j] = dp[i][j - 1] * p + c[j]; (5)联立(4)、(5) 得:2 <= j <= i: dp[i][j] = dp[i][j - 1] * p + c[j];由递推关系可知 :dp[i][i] = dp[i][1] * pow(p, i - 1) + tmp; (6)其中tmp = c[1] ^ (i - 1) + c[2] ^ (i - 2) + ... + c[i - 1];联立(3)、(6) 得:dp[i][i] = tmp / (1 - pow(p, i));回代得原式 :2 <= j < i: dp[i][j] = dp[i][j - 1] * p + c[j];最终解即为dp[n][m];
*/#include <stdio.h>
#include <string.h>
#define REP(i, a, b) for(int i = a; i <= b; ++i)
const double eps = 1e-5;
const int O = 2005;
double pp[O], dp[O][O], c[O], p1, p2, p3, p4, p, pp3, pp4;
int n, m, k;
void work(){if(1 - p1 - p2 < eps){//特判除数等于0的情况printf("%.5f\n", 0);return;}if(p4 < eps){//如果已经小于0.00001则直接输出0.00000printf("%.5f\n", 0);return;}p = p2 / (1 - p1);pp3 = p3 / (1 - p1);pp4 = p4 / (1 - p1);pp[0] = 1.0;REP(i, 0, n) dp[0][i] = dp[i][i] = 0;REP(i, 1, n) pp[i] = p * pp[i - 1];dp[1][1] = p4 / (1 - p1 - p2);REP(i, 2, n){REP(j, 1, i) c[j] = dp[i - 1][j - 1] * pp3 + (j <= k ? pp4 : 0);REP(j, 1, i) dp[i][i] += c[j] * pp[i - j];dp[i][i] /= (1 - pp[i]);dp[i][1] = dp[i][i] * p + c[1];REP(j, 2, i - 1) dp[i][j] = dp[i][j - 1] * p + c[j];}printf("%.5f\n", dp[n][m]);
}
int main(){while(~scanf("%d%d%d%lf%lf%lf%lf", &n, &m, &k, &p1, &p2, &p3, &p4)) work();return 0;
}
这篇关于【HDU】 4089 Activation 概率DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
