題干：

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?ith?door, it can either take you back to the same position where you begun in?xi?minutes, or can take you out of the maze after?xi?minutes. If you come back to the same position, you can't remember anything. So, every time you come to the beginning position, you have no past experience.

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 an integer?n (1 ≤ n ≤ 100)?denoting the number of doors. The next line contains?nspace separated integers. If the?ith?integer?(xi)?is positive, you can assume that the?ith?door will take you out of maze after?xi?minutes. If it's negative, then the?ith?door will take you back to the beginning position after?abs(xi)?minutes. You can safely assume that?1 ≤ abs(xi) ≤ 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?'inf'. Print the result in?p/q?format. Where?p?is the numerator of the result and?q?is the denominator of the result and they are relatively prime. See the samples for details.

Sample Input

3

1

1

2

-10 -3

3

3 -6 -9

Sample Output

Case 1: 1/1

Case 2: inf

Case 3: 18/1

題目大意：

在n個門前選擇一扇門出去， 然后如果第i扇門的 Xi值是正的話，你會花費Xi時間后出去 ， 如果Xi是負數(shù)的話你會花費-Xi時間后回到老地方，并且忘記了剛才的選擇， 選擇一扇門的概率是等概的。求出去的期望。

解題報告：

設任意選擇一個門，選擇到正權值的概率是P1，負權值的概率是P2，正權值的平均值是v1,負權值的平均值是v2，設要求的期望是E，那么，就可以找到一個方程來：

其實是找到了和如何回歸到原來的狀態(tài)，從而可以寫出方程。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int a[MAX]; int main() {int t,iCase=0;cin>>t;while(t--) {int zheng=0,fu=0,z=0,f=0,n;scanf("%d",&n);for(int i = 1; i<=n; i++) {scanf("%d",a+i);if(a[i] > 0) zheng += a[i],z++;else fu += -a[i],f++;;}printf("Case %d: ",++iCase);if(z == 0) {puts("inf");continue;}// zheng+fu/zint g = __gcd(zheng+fu,z);printf("%d/%d\n",(zheng+fu)/g,z/g);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【LightOJ - 1027】A Dangerous Maze（概率dp，数学期望）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。