1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
D - Redistribution.py 1.06 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/19
# @File : D - Redistribution.py
#基础线性DP,redistribution。3,4 、 4,3 、 7
def dp_redistribution():#优化的方法,用前缀和思路
dp = [1] * (2000 + 1)
dp[1] = 0
dp[2] = 0
# 初始化
a = 0
for i in range(3, 2000 + 1):
a += dp[i - 3]
dp[i] = a % (10 ** 9 + 7)
return dp[s]
def dp_redistribution1():
dp = [1] * (2000 + 1)
dp[1] = 0
dp[2] = 0
# 初始化
for i in range(3, 2000 + 1):
dp[i] = (dp[i - 1] + dp[i - 3]) % (10 ** 9 + 7)
return dp[s]
"""
对于每一个n,可以由与n相差大于等于3的前面全部的方法数相加得到,dp[n] = dp[n-3]+dp[n-4]+dp[n-5]+……+dp[0],所以dp[0]设置为1
又因为dp[n-1] = dp[n-4]+dp[n-5]+dp[n-6]+……+dp[0]
所以dp[n] = dp[n-3] + dp[n-1] 状态转移方程
细节:必须用2000代替s才能ac。。。
"""
if __name__ == '__main__':
s = int(input())
res = dp_redistribution()
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

搜索帮助