选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入一个正整数S。
输出最大的约数之和。
11
9
样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000题解：这不是一道打卡题了qwq！我觉得有点难想到是01背包啊。
恩要先预处理 a[i]，表示i的约数和
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> using namespace std; const int N=1002; int a[N],dp[N],n; int main(){ freopen("1734.in","r",stdin); freopen("1734.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n/2;i++) for(int j=2;j*i<=n;j++) a[i*j]+=i; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) dp[j]=max(dp[j],dp[j-i]+a[i]); printf("%d",dp[n]); return 0; }
原文：https://www.cnblogs.com/wuhu-JJJ/p/11715565.html