题目链接：https://vjudge.net/problem/LightOJ-1395

1395 - A Dangerous Maze (II)

Time Limit: 2 second(s)

Memory Limit: 32 MB

You are in a maze; seeing n doors in front of you in beginning. You can choose any door you like. The probability for choosing a door is equal for all doors.

If you choose the i^th door, it can either take you back to the same position where you begun in x_i minutes, or can take you out of the maze after x_i minutes. If you come back to the same position, you can remember last K doors you have chosen. And when you are about to choose a door, you never choose a door that is already visited by you. Or we can say that you never choose a door that is visited as one of the last K doors. And the probability of choosing any remaining door is equal.

Now you want to find the expected time to get out of the maze.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and two integers n K (1 ≤ n ≤ 100, 0 ≤ K ≤ n). The next line contains n space separated integers. If the i^th integer (x_i) is positive, you can assume that the i^th door will take you out of maze after x_i minutes. If it's negative, then the i^th door will take you back to the beginning position after abs(x_i) minutes. You can safely assume that 1 ≤ abs(x_i) ≤ 10000.

Output

For each case, print the case number and the expected time to get out of the maze. If it's impossible to get out of the maze, print '-1'. Otherwise print the result. Error less than 10^-6 will be ignored.

Sample Input

Output for Sample Input

2 0

10 10

2 0

10 -10

3 1

10 -10 -20

3 2

10 -10 -20

Case 1: 10

Case 2: 20.000

Case 3: 30.0000000000

Case 4: 25.0000000000

题意：

有n扇门，一扇门要么能在特定时间内把人带出迷宫，要么能在特定时间内把人带会原地，人能记住前k个选择，每扇门被选择的几率是相等的。问走出迷宫的平均时间。

题解：

1.LightOJ - 1027 A Dangerous Maze此题的强化版。

2.简称能把人带出去的为A门，带回原地的为B门。假设A门有cnt1扇，B门有cnt2扇，cost1为经过A门的平均时间，cost2为经过B门的平均时间。因为所有门被选中的概率是相等的，所以经过任意一扇A门所用的时间可用cost1代替，经过任意一扇B门所用的时间可用cost2代替。

3.人可以记住前k个选择，可知这k个选择必定都为B门。当k>cnt2时，即人能够把所有B门都记住并且还有剩余，但这些剩余是没用的，因为下一次选择必定是A门。所以只需考虑min(cnt2, k)。

4.取k = min(cnt2, k)，设dp[i]为：在记住了i个选择的状况下，走出去所需的平均时间。

当i==k时，dp[k] = (cnt1/(n-k))*cost1 + ( (cnt2-k)/(n-k))*(cost2+dp[k]) ，移项得：dp[k] = cost1 + ((cnt2-k)/cnt1)*cost2

当i < k时，dp[i] = (cnt1/(n-i))*cost1 + ((cnt2-i)/(n-i))*(cost2+dp[i+1]) 。

则dp[0]即为答案。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e5;

 const int MAXN = 1e2+;

 double dp[MAXN];

 int main()

 {

     int T, kase = , n, k;

     scanf("%d", &T);

     while(T--)

     {

         int cnt1 = , cnt2 = ;

         double cost1 = , cost2 = ;

         scanf("%d%d", &n,&k);

         for(int i = ; i<=n; i++)

         {

             int val;

             scanf("%d", &val);

             if(val>) cnt1++, cost1 += val;

             else cnt2++, cost2 -= val;

         }

         if(cnt1==)

         {

             printf("Case %d: %d\n", ++kase, -);

             continue;

         }

         if(cnt1==n)

         {

             printf("Case %d: %.8lf\n", ++kase, cost1/cnt1);

             continue;

         }

         cost1 /= cnt1;

         cost2 /= cnt2;

         k = min(k, cnt2);

         dp[k] = cost1 + 1.0*(cnt2-k)/cnt1*cost2;

         for(int i = k-; i>=; i--)

             dp[i] = 1.0*cnt1/(n-i)*cost1 + 1.0*(cnt2-i)/(n-i)*(cost2+dp[i+]);

         printf("Case %d: %.8f\n", ++kase, dp[]);

     }

 }

巴特西

LightOJ - 1395 A Dangerous Maze (II) —— 期望

Input

Output

Sample Input

Output for Sample Input

最新文章

热门文章