0

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.

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

In this game,

the players Foo and bar make an alternative move.

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.

Note:

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

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;
}

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 ?

4

1 回答 1

1

您可以做出的第一个观察是您不需要所有四个参数calculate- 其中两个是多余的，即它们包含的信息已经在其他两个参数中可用。（顺便说一句，我不确定性能是唯一的问题——我认为你没有正确模拟游戏，也许你应该在一些小测试用例上尝试一下。）

然后，在您删除了不必要的参数并将它们从0to减少到两个整数N - 1之后，您应该阅读有关memoization的内容- 这是一种避免多次执行相同计算的方法。例如，在您计算出 的答案后start = 2, end = 7，不必每次需要该值时都一遍又一遍地进行相同的计算，您可以将其存储在二维数组的第 2 行第 7 列中，并将其标记为找到. 这样，您将只计算每个子区间的答案一次，然后将其用作您已经知道的东西。

这将复杂性降低到O(N^2)，这取决于实现和测试机器，可能会或可能不会足够快以通过问题，但这是一个好的开始，并且具有教育价值 - 动态编程和记忆化经常使用，如果你没有，你应该学习它们。

于 2012-10-06T10:22:48.733 回答