EOJ 3446 题解

ultmaster edited 2 年,1 月前

题目自己看。

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

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

理由是,只有当掷了 枚骰子时总点数为 才有可能达到 。而对于 ,能达到 的概率恰好为

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

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

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

事实上,还有一种更方便的直接从 开始用两重 for 循环计算 的方法。这种 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;
    }

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

Comments

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