```cpp
/*
Name: luogu p1734
Copyright: @[冰晶](/user/214675)
Author: @[冰晶](/user/214675)
Date: 17/05/20 10:30
Description: 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大.
*/
#include<bits/stdc++.h>
using namespace std;
int n,a[1007],ans[1007];
int main()
{
cin>>n;
//求最大因数和
for(int i=1;i<=n/2;i++)
for(int j=2;i*j<=n;j++)
a[i*j]+=i;
//背包核心
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
//状态转移方程
ans[j]=max(ans[j],ans[j-i]+a[i]);
cout<<ans[n];
return 0;
}
```
by 07734_ @ 2020-05-17 10:36:01