202104-4 校门外的树

• 题目链接
• • 题型分析
  • 代码
  • 但运行超时，只能拿到60分，欢迎各位提问和改进！

题目链接

http://118.190.20.162/view.page?gpid=T125

题型分析

典型的DP问题

递推公式：
f[i] = f[i] + f[j] *calc(i,j)

含义：
aj - ai 表示到i为止的最后一个区间，其长度为d，该区间可以被分成以k为单位的区间。
k的取值范围是q[d] （小于d的所有约数）
f[i] 表示到第i个障碍物前已有的方案数
calc(j，i) 表示第j个障碍物到第i个障碍物之间的方案数

初始化：
f[0] = 1

代码思路：
首先求出1-M之间每个数的约数，将其存储在q中备用。
从第二个障碍物起开始计算，由于方案不能重复，因此需要设置一个st的布尔数组用于记录哪些k已经使用，注意！每一轮都要重新初始化st。
从后往前遍历j。
对于每一个j，需要计算与i的距离d，针对距离d中可以选取的所有k进行遍历，如果该k没有被访问，res+1并将其对应的st[k]=False。
此处需要注意st[d]要设置成True！！【这里我也很疑惑，欢迎大佬评论区解答】
接下来利用递推公式计算f[i]

f[n-1]即为最终方案数！

代码

# 校门外的树
n = int(input())
a = list(map(int, input().split()))

N = n+1
M = a[-1]+1

MOD = 1e9 + 7

f = [0 for i in range(N)]  # 存储状态
q = [[] for i in range(M)]  # 存储每个数的约数[因数]
# 求1-M之间每个数的约数
for i in range(1, M):
    j = i * 2
    while j < M:
        q[j].append(i)
        j += i
f[0] = 1
for i in range(1, n):
    st = [False for i in range(M)]  # bool数组  用于存储该k是否被用过 每次初始化一下st数组
    for j in range(i - 1, -1, -1):
        d = a[i] - a[j]  # 计算一下a[i]到a[j]的距离
        res = 0
        # 枚举一下d的所有约数
 
        for k in q[d]:
            if st[k]!=True:
                res += 1
                st[k] = True
        st[d] = True
        f[i] = (f[i] + f[j] * res) % MOD
print(int(f[n - 1]))

但运行超时，只能拿到60分，欢迎各位提问和改进！