0

Foo と Bar は戦略ゲームをしています。ゲーム開始時、N 個のりんごが一列に（一直線に）並んでいます。リンゴには 1 から N までの番号が付けられています。各リンゴには特定の価格値があります。

i 番目のリンゴの価格は、i=1 から N までのpiです。

このゲームでは、

プレーヤーの Foo と bar は別の動きをします。

各動きで、プレーヤーは次のことを行います。 -リンゴが1つしか残っていない場合、プレーヤーはコインを投げ、表の場合、プレーヤーは現在一列に並んでいるリンゴの中で最初のリンゴを取ります。それ以外の場合、最後のリンゴはプレーヤーによって取られます。

ここでの目標は、予想される合計価格値を計算することです。Foo が最初にプレイした場合に Foo が取得します。

注:

コインは公平です。表の確率は 0.50 で、裏の確率も同様です。合計価格値 = すべてのリンゴの価格値の合計、Foo が取得します。

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

次のコードを書きました。

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

しかし、上記のコードは、制約がリンゴの価格<=1000および1<=N<=2000であり、500のテストケースがあるため、非常に遅いです。

効率的な方法でそれを解決する方法は？

4

1 に答える 1

1

最初に確認できることは、4 つcalculateの引数すべてが必要というわけではないということです。そのうちの 2 つは冗長です。つまり、それらに含まれる情報は、他の 2 つの引数で既に利用可能です。(ちなみに、パフォーマンスが唯一の問題かどうかはわかりません。ゲームを正しくシミュレートしていないと思います。小さなテスト ケースで試してみてください。)

次に、不要なパラメータを削除して から までの 2 つの整数に減らした後、0メモ化N - 1について読む必要があります。これは、同じ計算を複数回実行することを避ける方法です。たとえば、 の答えを計算した後、この値が必要になるたびに同じ計算を何度も行うのではなく、2 次元配列の 2 行 7 列に格納して、見つかったものとしてマークすることができます。 . このようにして、各サブインターバルの答えを 1 回だけ計算し、それを既に知っているものとして使用します。start = 2, end = 7

これは複雑さO(N^2)を、まだ学習していない場合は学習する必要があります。

于 2012-10-06T10:22:48.733 に答える