P1734 最大约数和

题目描述

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

输入格式

输入一个正整数 S。

输出格式

输出最大的约数之和。

输入输出样例

输入 

11

输出 

9

说明/提示

【样例说明】

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

【数据规模】

对于 100%的数据，1≤S≤1000。

代码实现

#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N];int main(){int n;cin>>n;for(int i=1;i<=n/2;i++)    //记录每个小于n的数的约数之和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++){     //j就是背包容量，a[i]是物品价值 f[j]=max(f[j],f[j-i]+a[i]);}}cout<<f[n]<<endl;return 0;
}