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


【题解】:北京现场赛的I题,由于当时状态没有设好,所以没有做出来。
              本题的转移比较明显,关键是转移中存在两个环,如何处理掉环成为了解题的关键。
              设dp[i][j] 表示队列中有i个人,tomato排在j位置发生满足条件事件的概率。
              显然dp[n][m]即为所求。

              转移:
              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];

              第一个环移项即可处理,第二个环需要无限迭代先算出dp[i][1]和dp[i][i],然后for一遍算出dp[i][j], 2<=j<i;
              整体复杂度是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, 0sizeof(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 }