EOJ 3446 题解

ultmaster edited 2 年,8 月前

题目自己看。

30 分到 70 分其实没啥区别,蒙特卡洛模拟都能过,精度控得好一点多交几发 70 分就稳了。此题 SPJ (Special Judge),只要答案误差满足要求,输出多少位不作要求。

考虑 $f(i,j)$ 表示总共在掷了 $i$ 枚骰子的前提下,获得总点数为 $j$ 的方案数。那么当 $j$ 较大时,显然有:

$$f(i,j)=\sum_{k=1}^6 \frac{1}{6}f(i-1,j-k)$$

理由是,只有当掷了 $i-1$ 枚骰子时总点数为 $j-1,j-2,\ldots,j-6$ 才有可能达到 $f(i,j)$。而对于 $f(i-1,j-k)$,能达到 $f(i,j)$ 的概率恰好为 $\frac{1}{6}$。

当 $j$ 较小时,显然对于 $k>j$ 的情况是不可能的,判断一下就好了。

很遗憾,如果直接递归搜索的话复杂度是指数级别的,肯定会超时。我们可以采用记忆化搜索,即对于每个计算过的 $f(i,j)$ 都存在一个对应的 $g[i][j]$ 数组中。

程序一开始的时候,可以把 $g[i][j]$ 全部赋值为小于 0 的数。下次再计算某 $f(i,j)$ 如果发现已经计算过($g[i][j]>0$),那么就不用再次计算了,直接返回结果就可以。那么这样的话,其实每一个 $f(i,j)$ 最多计算了一次,又因为这个计算是常数级别的,总复杂度就降到了 $O(n^2)$,足够通过本题。

事实上,还有一种更方便的直接从 $i=0,j=0$ 开始用两重 for 循环计算 $g[i][j]$ 的方法。这种 Bottom-up 的策略,我们一般称为 DP (Dynamic Programming),有兴趣的同学可以自行上网查找相关资料,这里只给出核心代码:

for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= 6 * n; ++j) {
        for (int t = 1; t <= min(6, j); ++t)
            g[i][j] += g[i - 1][j - t];
        g[i][j] /= 6;
    }

哦对了,此题还有一个坑点,就是当 $k>6n$ 的时候,直接输出 $0$ 就好了。

Comments

你当前正在回复 博客/题目
存在问题!