概率dp-hdu-4089-Activation

題目意思：   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;
}