P1734 最大约数和

选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入一个正整数S。

输出最大的约数之和。

11

9

样例说明

取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。

数据规模

S<=1000

同样的，我们一上来需要有一个基础的解题框架：按题目样例给的数字11来说，4+6不超过11，同样也不超过10，所以数字10的答案也是9。这就很容易让我们想到这题的动态规划解法：假设dp[n]是数字n的答案那么这里也就是说dp[11]=dp[10]，这里我们能看到递归的影子，选不选数字 i 取决于选了之后是否比不选的大。也就是 ： dp [ j ] = max（dp[j],dp[j-i]+a[i]）这个过程应该从1一直遍历到n，每次遍历又需要从i+1 到 n 遍历，这max里面的dp[ j ]就是上一次遍历的结果，如果取的是dp[ j ]说明和上一次结果一样取法，反之就是取了j-i 和 i

上python代码，看代码或许容易理解：

n = int(input())
a = [0 for i in range(10001)]
dp = [0 for j in range(10001)]
for i in range(1, n // 2 + 1):
    for j in range(2, n):
        if i * j > n:
            break
        a[i * j] += i

for i in range(1, n + 1):
    for j in range(i, n + 1):
        dp[j] = max(dp[j], dp[j - i] + a[i])
print(dp[n])