11年北京現場賽的題目。機率DP。 公式化簡起來比較困難。。。。而且就算結果做出來了，沒有考慮特殊情況照樣會WA到死的。。。。 去參加區域賽一定要考慮到各種情況。 像機率dp，公式推出來就很容易寫出來了。
1 /*
2 HDU 4098
3 題意：有n個人排隊等着在官網上激活遊戲。Tomato排在第m個。
4 對于隊列中的第一個人。有一下情況：
5 1、激活失敗，留在隊列中等待下一次激活（機率為p1)
6 2、失去連接配接，出隊列，然後排在隊列的最後（機率為p2）
7 3、激活成功，離開隊列（機率為p3）
8 4、伺服器癱瘓，伺服器停止激活，所有人都無法激活了。
9 求伺服器癱瘓時Tomato在隊列中的位置<=k的機率
10
11 解析：
12 機率DP；
13 設dp[i][j]表示i個人排隊,Tomato排在第j個位置，達到目标狀态的機率(j<=i)
14 dp[n][m]就是所求
15 j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4;
16 2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4;
17 k<j<=i: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1];
18 化簡：
19 j==1: dp[i][1]=p*dp[i][i]+p41;
20 2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41;
21 k<j<=i: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1];
22
23 其中:
24 p=p2/(1-p1);
25 p31=p3/(1-p1)
26 p41=p4/(1-p1)
27
28 可以循環i=1->n 遞推求解dp[i].在求解dp[i]的時候dp[i-1]就相當于常數了。
29 在求解dp[i][1~i]時等到下列i個方程
30 j==1: dp[i][1]=p*dp[i][i]+c[1];
31 2<=j<=k:dp[i][j]=p*dp[i][j-1]+c[j];
32 k<j=i: dp[i][j]=p*dp[i][j]+c[j];
33 其中c[j]都是常數了。上述方程可以解出dp[i]了。
34 首先是疊代得到 dp[i][i].然後再代入就可以得到所有的dp[i]了。
35
36 注意特判一種情況。就是p4<eps時候，就不會崩潰了，應該直接輸出0
37 */
38 #include<stdio.h>
39 #include<iostream>
40 #include<math.h>
41 #include<algorithm>
42 #include<string.h>
43 using namespace std;
44
45 const int MAXN=2020;
46 const double eps=1e-5;
47 double c[MAXN];
48 double pp[MAXN];
49 double dp[MAXN][MAXN];
50 int main()
51 {
52 int n,m,k;
53 double p1,p2,p3,p4;
54 while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF)
55 {
56 if(p4<eps)
57 {
58 printf("0.00000\n");
59 continue;
60 }
61 double p=p2/(1-p1);
62 double p41=p4/(1-p1);
63 double p31=p3/(1-p1);
64 pp[0]=1.0;//pp[i]=p^1;
65 for(int i=1;i<=n;i++) pp[i]=p*pp[i-1];
66
67 dp[1][1]=p41/(1-p);
68 c[1]=p41;
69 for(int i=2;i<=n;i++)
70 {
71 for(int j=2;j<=k;j++)c[j]=p31*dp[i-1][j-1]+p41;
72 for(int j=k+1;j<=i;j++) c[j]=p31*dp[i-1][j-1];
73 double tmp=c[1]*pp[i-1];
74 for(int j=2;j<=k;j++)tmp+=c[j]*pp[i-j];
75 for(int j=k+1;j<=i;j++)tmp+=c[j]*pp[i-j];
76 dp[i][i]=tmp/(1-pp[i]);
77 dp[i][1]=p*dp[i][i]+c[1];
78 for(int j=2;j<i;j++)dp[i][j]=p*dp[i][j-1]+c[j];
79 }
80 printf("%.5lf\n",dp[n][m]);
81 }
82 return 0;
83 }