0

在尝试提高我对本次比赛的回答速度时，我有一个函数，它接受两个值n并k产生一个输出。计算是重复的，所以我要记住它。我不能使用二维数组，因为nand的约束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 回答
0

您不必存储二维值数组。代替记忆，扭转问题并改用动态编程。

为了节省一些时间，请注意f(x, y) = 0如果x <= y.

计算f(i, 0)for的值1 <= i <= x - k并将它们存储到一维数组中。然后计算f(i, 1)、2 <= i <= x - k + 1等f(i, 2)，3 <= i <= x - k + 2直到f(i, k - 1)得到k <= i <= x - 1。然后就可以计算了f(x, k)。在每一步，您只需要两个长度数组x - k。

计算f(i, j)需要i - j - 1加法和除法。所以总时间是 ϴ((x - k) 2 k)。但是如果你先计算总和然后除法会更快，因为每个总和只是比前一个多一个元素，所以总时间是 ϴ((x - k) k)。

于 2013-03-07T22:30:14.260 回答