Random Sequence
时间限制：1s 空间限制：128MB
题目描述
There is a random sequence L whose element are all random numbers either -1 or 1 with the same possibility. Now we define MAVS, the abbreviate of Maximum Absolute Value Subsequence, to be any (if more than one) subsequences of L whose absolute value is maximum among all subsequences. Given the length of L, your task is to find the expectation of the absolute value of MAVS.
输入格式
There is only one input file. The first line is the number of test cases T. T positive integers follow, each of which contains one positive number not greater than 1500 denoted the length of L.
给你一个数字L,代表数字串长。这个数字串每个元素为1或-1.
那么就有这个数列有2^L种可能。
现对每个可能的数字串，求其连续子串和，并将和取绝对值，记下最大的那个值。
再求出所有这些值的总和。
输入总和/2^L
输出格式
For each test case, output the expectation you are required to calculate. Answers are rounded to 6 numbers after the decimal point.(as shown in the sample output)
样例输入
3 1 5 10
样例输出
Case 1: 1.000000 Case 2: 2.750000 Case 3: 4.167969
提示
当输入2时，有
1 1
1 -1
-1 1
-1 -1
这四种可能，其对应的值分别为(2+1+1+2)=6
6/4=1.5
题目来源
acm 2011 福州