程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 概率dp-hdu-4089-Activation

概率dp-hdu-4089-Activation

編輯:C++入門知識

題目意思:   n個人排隊嘗試游戲,隊首中有四種情況。   1、動作失敗重新連,隊列不變,概率為p1.   2、服務器鏈接失敗重新連,第一個人排到隊尾,概率為p2.   3、連接成功,第一個人出隊,概率為p3.   4、服務器崩塌,終止,概率為p4.   求某人排在第m的位置,求服務器崩塌時他前面有少於k個人的概率。   解題思路:   之前做過類似的概率dp,有迭代,高斯消元解方程,不是順序的,不過沒寫博客,所以就沒做出來。。囧   因為人數有變化,所以人數要設一維,然後該人的位置也在變化,設為第二維。   dp[i][j]表示共有i個人,該人排在第j的位置時,發生所求事件的概率。   當j==1時,該人有1、2、4三種選擇,dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4   當2=<j<=k時,第一個人有1、2、3、4中選擇使得事件發生,dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4   當j>k時,第一個人有1、2、3種選擇使得事件發生,dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1],   化簡得:   j==1 dp[i][j]=pp2*dp[i][i]+pp4   2=<j<=k dp[i][j]=pp2*dp[i][j-1]+pp3*dp[i-1][j-1]+pp4   j>k時,dp[i][j]=pp2*dp[i][j-1]+pp3*dp[i-1][j-1]   dp[1][1]可以直接求。   從dp[1]遞推求出dp[i]   然後對於每一個dp[i]      ,先把其他未知數帶入dp[i][j]方程,迭代求出dp[i][j].   然後用依次遞推求出dp[i][j].   代碼:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-8
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;


//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
#define Maxn 2005

double dp[Maxn][Maxn]; //dp[i][j]表示一共有i個人,該人排在第j位時的發生所求事件的概率
double p1,p2,p3,p4,temp[Maxn]; //temp[i]表示求dp[i][j] 時前面一層的常數
double pp[Maxn];//pp[i]表示pp^i,用於迭代求出dp[i][i];
int n,m,k;

int main()
{
   double pp2,pp3,pp4;

   while(~scanf("%d%d%d",&n,&m,&k))
   {
      scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);
      if(p4<=eps) //最後一步肯定要*P4 ,如果p4很小的話,直接輸出0.00000
      {
         puts("0.00000");
         continue;
      }

      pp2=p2/(1-p1);pp3=p3/(1-p1);
      pp4=p4/(1-p1);

      pp[0]=1.0;
      for(int i=1;i<=n;i++)
         pp[i]=pp[i-1]*pp2; //用於迭代保存系數
      dp[1][1]=p4/(1-p1-p2); //根據方程1很快可以求出
      for(int i=2;i<=n;i++)
      {
         temp[1]=pp4;
         for(int j=2;j<=k;j++)
            temp[j]=pp3*dp[i-1][j-1]+pp4;
         for(int j=k+1;j<=i;j++)
            temp[j]=pp3*dp[i-1][j-1];//第j個方程的常數
         double tmp=0.0;//求出只含dp[i][i]未知數方程的常數部分

         for(int j=i;j>=1;j--)
            tmp+=temp[j]*pp[i-j]; //把前面的方程帶入後面的方程中
         dp[i][i]=tmp/(1-pp[i]);
         dp[i][1]=pp2*dp[i][i]+temp[1]; //帶入方程求出後面未知數的值
         for(int j=2;j<i;j++)
            dp[i][j]=pp2*dp[i][j-1]+temp[j];
      }
      printf("%0.5f\n",dp[n][m]);
   }
   return 0;
}

 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved