1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
cses Dice Combinations.py 1.47 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/18
# @File : cses Dice Combinations.py
# https://cses.fi/problemset/task/1633/
#基础线性DP,骰子组合
def dp_dice1():#优化的方法,用前缀和思路代替SUM函数操作
dp = [1]
a = 1
for i in range(1, n + 1):
if i <= dice:
dp.append(a)
a += dp[i]
else:
a -= dp[i - dice - 1]
dp.append(a % (10 ** 9 + 7))
a += dp[i]
return dp[-1]
def dp_dice():
dp = [1] * (n + 1)
for i in range(1, n + 1):
if i <= dice:
dp[i] = sum(dp[:i])
else:
dp[i] = sum(dp[i - dice:i]) % (10 ** 9 + 7)
return dp[n]
"""
由于这个数实在是太大的,一个列表格子都装不下这么大的数,所以在过程中也要进行取模操作,不能就只在最后输出结果的时候取模,这样会RE。
"""
"""
思路:对于每一个n,都可以由n-6、n-5、……、n-1的六种方法数相加得到,因为他们再抛一次骰子(六种可能)就可以得到n。
细节:n小于等于6和大于6的处理不一样。因为前者可以由一次抛骰子得到,所以初始化的时候dp[0]要设为1。
n小于等于6时:每一个n都由前面的全部的方法数相加得到,因为前面的总共都不到6个数
"""
if __name__ == '__main__':
n = int(input())
dice = 6
res = dp_dice()
print(res % (10 ** 9 + 7))
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助