【題意】：
有n人都是仙劍5的fans，現(xiàn)在要在官網(wǎng)上激活游戲，n個(gè)人排成一個(gè)隊(duì)列（其中主角Tomato最初排名為m），
對于隊(duì)列中的第一個(gè)人，在激活的時(shí)候有以下五種情況：
1.激活失敗：留在隊(duì)列中繼續(xù)等待下一次激活（概率p1）
2.失去連接：激活失敗，并且出隊(duì)列然后排到隊(duì)列的尾部（概率p2）
3.激活成功：出隊(duì)列（概率p3）
4.服務(wù)器癱：服務(wù)器停止服務(wù)了，所有人都無法激活了（概率p4）
求服務(wù)器癱瘓并且此時(shí)Tomato的排名<=k的概率。【題解】：北京現(xiàn)場賽的I題，由于當(dāng)時(shí)狀態(tài)沒有設(shè)好，所以沒有做出來。
本題的轉(zhuǎn)移比較明顯，關(guān)鍵是轉(zhuǎn)移中存在兩個(gè)環(huán)，如何處理掉環(huán)成為了解題的關(guān)鍵。
設(shè)dp[i][j] 表示隊(duì)列中有i個(gè)人，tomato排在j位置發(fā)生滿足條件事件的概率。
顯然dp[n][m]即為所求。
轉(zhuǎn)移：
j == 1: dp[i][1] = p1 * dp[i][1] + p2 * dp[i][i] + p4;
2 <= j <= k: dp[i][j] = p1 * dp[i][j] + p2 * dp[i][j-1] + p3 * dp[i-1][j-1] + p4;
k < j <= i: dp[i][j] = p1 * dp[i][j] + p2 * dp[i][j-1] + p3 * dp[i-1][j-1];
第一個(gè)環(huán)移項(xiàng)即可處理，第二個(gè)環(huán)需要無限迭代先算出dp[i][1]和dp[i][i]，然后for一遍算出dp[i][j], 2<=j<i;
整體復(fù)雜度是O(n^2).
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 const double eps = 1e-8;
6 int n, m, k;
7 double p1, p2, p3, p4;
8 double dp[2010][2010], c[2010], p[2010];
9
10 void solve() {
11 memset(dp, 0, sizeof(dp));
12 double p21 = p2 / (1 - p1);
13 double p31 = p3 / (1 - p1);
14 double p41 = p4 / (1 - p1);
15 dp[1][1] = p4 / (1 - p1 - p2);
16 c[1] = p41;
17 p[0] = 1;
18 for(int i = 1; i <= n; i++) p[i] = p[i-1] * p21;//p[i] = p21 ^ i;
19 for(int i = 2; i <= n; i++) {
20 for(int j = 2; j <= k; j++)
21 c[j] = p31 * dp[i-1][j-1] + p41;
22 for(int j = k + 1; j <= i; j++)
23 c[j] = p31 * dp[i-1][j-1];
24 double tmp = c[i];
25 for(int j = i - 1; j; j--) {
26 tmp += p[i-j] * c[j];
27 }
28 dp[i][i] = tmp / (1 - p[i]);
29 dp[i][1] = p21 * dp[i][i] + c[1];
30 for(int j = 2; j <= i; j++)
31 dp[i][j] = p21 * dp[i][j-1] + c[j];
32 }
33 printf("%.5f\n", dp[n][m]);
34 }
35 int main() {
36 while(~scanf("%d%d%d", &n, &m, &k)) {
37 scanf("%lf%lf%lf%lf", &p1, &p2, &p3, &p4);
38 if(p4 < eps) {//特判一下，如果p4很小直接輸出0.00000
39 puts("0.00000");
40 continue;
41 } else solve();
42 }
43 return 0;
44 }