1.1 题目描述

有一排硬币堆，两个人轮流取硬币。每个选手随机取最左边或者最右边的一堆硬币。求先手期

望取得的硬币数。

1.2 输入格式

本题有多组测试数据。

第一行一个数 T ，表示数据组数。

对于每组测试数据，第一行一个正整数 n，表示有多少堆硬币。

第二行 n个非负整数，依次表示每一堆硬币的个数。

1.3 输出格式

对于每组测试数据，输出一行一个数，表示先手期望取得的硬币数。保留 3 位小数。

1.4 样例输入

2

3

1 4 9

4

5 5 5 5

1.5 样例输出

9.500

10.000

1.6 样例解释

对于第一个测试数据：

先手第一次取 后手第一次取 先手第二次取 先手取得的石子数 出现的概率

1 4 9 10 0.25

1 9 4 5 0.25

9 1 4 13 0.25

9 4 1 10 0.25

所以先手期望取得的硬币数为：

10 × 0.25 + 5 × 0.25 + 13 × 0.25 + 10 × 0.25 = 9.5

对于第二个测试数据：

由于两个人都会取 2 堆石子，且每堆石子都是 5 个，所以无论怎么取答案都是 10。

1.7 数据范围

对于 30%的数据：n ≤ 10, T ≤ 5

对于 60%的数据：T ≤ 10

对于 100%的数据：n ≤ 1000, T ≤ 1000，每一堆的个数≤ 10^3

 

我们可以发现，取的概率只与位置有关，所以可以预处理出一个数组。

而取到这个数的概率即是1-上一次取的人取到这个数的概率

f[i,j]表示长度为i的时候第j位取到的概率。

这个dp相当于是反着做的，就是从长度小的推到长度大的，原因是我们初始的时候只能知道一个元素的概率，f[i]相当于在f[i-1]上面加一个。

但是我们推的时候还是要正着推。

于是对于一个长为i的，我可能取第一个也可能取最后一个，概率是相等的，都是1/2，于是就到了i-1的阶段。

当前取到j的概率就是i-1时对方没有取到j的概率，若取了最后一个，则i-1时所有编号都没变，若取了第一个，则所有编号减一。

于是萝莉跟我讲了两次蛋蛋讲了三次+，痛苦 = =。明明上次听懂了啊，看来总结还是真的很重要。

var   i,j,t,n,x:longint;   ans:extended;   f:array[0..1001,0..1001]of extended;begin     assign(input,'coin.in');     assign(output,'coin.out');     reset(input);     rewrite(output);     readln(t);     for i:=1 to 1000 do      for j:=1 to i do      f[i,j]:=1-0.5*(f[i-1,j]+f[i-1,j-1]);     for t:=1 to t do     begin          readln(n);          ans:=0;          for i:=1 to n do          begin               read(x);               ans:=ans+f[n,i]*x;          end;          writeln(ans:0:3);     end;     close(input);     close(output);end.