首页 > 代码库 > hdu4089(公式推导)概率dp

hdu4089(公式推导)概率dp

2024-07-07 17:05:16   228人阅读

题意：有n人都是仙剑5的fans，现在要在官网上激活游戏，n个人排成一个队列（其中主角Tomato最初排名为m），
    对于队列中的第一个人，在激活的时候有以下五种情况：
    1.激活失败：留在队列中继续等待下一次激活（概率p1）
    2.失去连接：激活失败，并且出队列然后排到队列的尾部（概率p2）
    3.激活成功：出队列（概率p3）
    4.服务器瘫：服务器停止服务了，所有人都无法激活了（概率p4）

求服务器瘫痪并且此时Tomato的排名<=k的概率。


解法：ans[i][j]表示i个人出于第j个位置要到目的状态的概率。转移需要推出并化简公式。贴一份原创题解：http://blog.csdn.net/morgan_xww/article/details/6920236


自己的代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=2002;
const int INF=1000000007;

double ans[Max][Max];
double p21,p31,p41;
int n,m,k;
double p1,p2,p3,p4;
long double after[Max];
int main()
{
    while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF)
    {
        if ( fabs(1 - p1 - p2) < 1e-9 )
        {
            puts("0.00000");
            continue;
        }
        p21=p2/(1.0-p1);
        p31=p3/(1.0-p1);
        p41=p4/(1.0-p1);
        ans[1][1]=p4/(1-p1-p2);
        for(int i=2;i<=n;i++)
        {
            after[1]=p41;
            for(int j=2;j<=k;j++)
                after[j]=p31*ans[i-1][j-1]+p41;
            for(int j=k+1;j<=i;j++)
                after[j]=p31*ans[i-1][j-1];
            double sum=0;
            for(int j=2;j<=i;j++)
            sum=sum*p21+after[j];
            sum=sum*p21+after[1];
            ans[i][1]=sum/(1-pow(p21,i));
            for(int j=2;j<=i;j++)
                ans[i][j]=p21*ans[i][j-1]+after[j];
        }
        printf("%.5lf\n",ans[n][m]);
    }
    return 0;
}


联系
我们