0

このコンテストの回答の速度を上げようとしているときに、2 つの値を取り、出力を生成する関数がありnますk。計算が繰り返されるのでメモしておきます。nとの制約kが10^5! だから私はマップを使用しています：

std::map<std::pair<int,int>,double> m;

double solve(int n, int k)
{
    if(k==0) return n;
    if(k==1) return (n-1)/2.0;

    std::pair<int,int> p = std::make_pair(n,k);
    std::map<std::pair<int,int>,double>::iterator it;

    if( (it=m.find(p)) != m.end())
        return it->second;

    double ans = 0;
    for(int i=1 ; i<=n-1 ; i++)
        ans += solve(i,k-1);
    ans = ans/n;
    m[p] = ans;

    return ans;
}

しかし、明らかに、このアプローチは遅すぎます。私のメモ化に何か問題がありますか？または、マップからの対数フェッチではなく、配列のような一定時間のフェッチを取得できますか?

この関数は、この繰り返しを解決します。

方式

f(x,0) = xとf(x,1) = (x-1)/2

これはより良い方法で解決できますか？よろしくお願いします。

4

2 に答える 2

2

マイナーな改善: find によって返された反復子を記憶し、operator[] を使用する代わりにそれを逆参照します。

于 2013-03-06T19:40:09.493 に答える