Foo和Bar是玩战略游戏。在比赛开始时，     有ñ苹果，摆成一排（直线）。苹果是     编号从1到N每一个苹果都有一个特定的价格值。

Foo and Bar is playing a game of strategy. At the start of the game, there are N apples, placed in a row (in straight line). The apples are numbered from 1 to N. Each apple has a particular price value.

第i个苹果的价格是 PI 对于i = 1到N。

The price of ith apple is pi for i=1 to N.

在这个游戏中，

玩家Foo和酒吧进行替代的举动。

the players Foo and bar make an alternative move.

在每次移动，玩家将执行以下操作：      - 如果仅存在一个苹果左，玩家抛硬币，如果它的      头，玩家需要的是苹果第一批苹果     目前present在一排在一条直线上，否则，最后是苹果     采取由玩家

In each move, the player does the following: -If there is only one apple left, the player toss the coin and if its head, the player takes the first apple among the apples that are currently present in a row in a straight line , otherwise, the last apple is taken by the player.

这里的目标是计算预计总价值，富会     如果富剧第一。

The goal here is to calculate the expected total price value, Foo will get if Foo Plays First.

注意

硬币是无偏。     头的概率是0.50和类似是尾部的概率。     总价值=所有的苹果的价格价值总和，富会。

The coin is Unbiased. Probability of head is 0.50 and similar is the probability of tail. Total Price Value=summation of price value of all the apples, Foo will get.

Example 1:
N=5
Apple price val: 
5 2 3 1 5 

Answer is : 11.00

Example 2:
N=6
7 8 2 3 7 8

Answer : 21.250


Example 3:
N=3
1 4 9

First           Second      Third          Foo Total Val
Foo gets 1  Bar gets 4  Foo gets 9          10
Foo gets 1  Bar gets 9  Foo gets 4          5
Foo gets 9  Bar gets 1  Foo gets 4          13
Foo gets 9  Bar gets 4  Foo gets 1          10

probability 0.5 • 0.5 = 0.25. 
Expected value (Foo)= (0.25 *10 )+ (0.25 *5) + (0.25*13)+ (0.25*10) = 9.500

我写了下面code：

I wrote the following code:

#include<iostream>
using namespace std;
double calculate(int start,int end,int num,int current);
int arr[2010];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=0;t<T;t++)
    {
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("%.3lf\n",calculate(0,N-1,N/2+N%2,0));   
    }

    return 0;
}
double calculate(int start,int end,int num,int current)
{
    if(num==current)
        return 0;
    double  value=0;
    value=.5*arr[start]+.5*arr[end]+.5*calculate(start+1,end,num,current+1)+.5*calculate(start,end-1,num,current+1);
    return value;
}

但上面的code是相当缓慢的，作为约束苹果＆LT的价格= 1000         1＆LT; = N＆LT; = 2000，有500个测试案例

But the above code is quite slow ,as the constraints are price of apple<=1000 and 1<=N<=2000 and there are 500 test cases.

如何解决它必须有效的方式？

How to solve it in must efficient way ?

推荐答案

第一个观察，你可以提出的是，你并不需要所有四个参数计算 - 两对他们是多余的，即它们所包含的信息是在另外两个参数已经可用。 （顺便说一句，我不知道性能是唯一的问题 - 我不认为你正确地模拟游戏中，也许你应该尝试一下在一些小的测试案例）

The first observation you can make is that you don't need all four arguments to calculate - two of them are redundant, i.e. the information they contain is already available in the other two arguments. (By the way, I'm not sure that performance is the only problem - I don't think you simulate the game correctly, maybe you should try it on some small test cases.)

然后，您已删除了不必要的参数，并带他们到两个整数从 0 来后 N - 1 ，你应该阅读有关记忆化 - 这是一种避免做同样的计算多次。例如，当你计算出来的答案启动2月底=的=，7 ，而不是每次你需要这个值的时间做相同的计算一遍又一遍，你可以存储第二行的两维阵列，第7列中并将其标记为找到。这样，你会计算每个子答案只有一次，然后用它的东西你已经知道了。

Then, after you've removed the unnecessary parameters and brought them down to two integers from 0 to N - 1, you should read about memoization - it's a way to avoid doing the same calculations multiple times. For example, after you've calculated the answer for start = 2, end = 7, instead of doing the same calculations over and over again every time you need this value, you can store in the 2nd row, 7th column of a two-dimensional array and mark it as found. This way you'll calculate the answer for each subinterval only once, and then use it as something you already know.

此带来的复杂性降低到 O（N ^ 2），其中，根据不同的实施和试验机，可以是或不是足够快，以传递的问题，但它是一个良好的开端，并具有教育价值 - 动态规划和记忆化使用pretty的时候，你应该学习他们，如果你还没有

This brings the complexity down to O(N^2), which, depending on the implementation and the testing machine, may or may not be fast enough to pass the problem, but is a good start, and has an educational value - dynamic programming and memoization are used pretty often, and you should learn them if you haven't.