题目描述：
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入格式：
输入一个正整数S。
输出格式：
输出最大的约数之和。
输入输出样例：
输入 #1复制
11
输出 #1复制
9
说明/提示：
样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000
AC Code：
#include<bits/stdc++.h> using namespace std; #define N 1010 int n,dp[N],sum[N],ans; int main() { scanf("%d",&n); for(int i=1;i<=n/2;i++) { for(int j=2;i*j<=n;j++) { //i*j=当前数，那么i必为当前数的约数 sum[i*j]+=i;//sum数组记录每个数的约数和 } } for(int i=1;i<=n;i++) { for(int j=n;j>=i;j--) {//模拟01背包，每个数只能使用1次 dp[j]=max(dp[j],dp[j-i]+sum[i]);//减去当前数，加上它的约数和 } } printf("%d\n",dp[n]); return 0; }
