题解 1909: 蓝桥杯算法提高VIP-拿糖果-python

解题思路:
动态规划
注意事项:
注意超时！
参考代码:

import math
def zys(n,zs):  #计算质因数
   res =[]
   d = math.sqrt(n)
   for i in zs:
       if n % i == 0 and i <= d:
           res.append(i)
   return res
N = int(input())
zs = []
d = int(math.sqrt(N))
for i in range(2, d+1):  #计算质数
   k = 0
   for j in range(2, i):
       if i % j == 0:
           k = 1
           break
   if k == 0:
       zs.append(i)
dp = [0] * (N+1)
for i in range(2,N+1):
   res = zys(i,zs)
   d = math.sqrt(i)
   for j in res:
       dp[i] = max(dp[i],j+dp[i-2*j])
print(dp[-1])