温州网站建设模板总部,wordpress怎么精简,做网站的方法,wordpress 分类目录描述显示题目描述
选取和不超过 S 的若干个不同的正整数#xff0c;使得所有数的约数#xff08;不含它本身#xff09;之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
输入
11
输出
9
说明/提示
【样例说明】
取数字 4 和 6使得所有数的约数不含它本身之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
输入
11
输出
9
说明/提示
【样例说明】
取数字 4 和 6可以得到最大值 (12)(123)9
【数据规模】
对于 100%的数据1≤S≤1000。
代码实现
#includeiostream
using namespace std;
const int N1010;
int a[N],f[N];int main(){int n;cinn;for(int i1;in/2;i) //记录每个小于n的数的约数之和for(int j2;i*jn;j)a[i*j]i; for(int i1;in;i){for(int ji;jn;j){ //j就是背包容量a[i]是物品价值 f[j]max(f[j],f[j-i]a[i]);}}coutf[n]endl;return 0;
}
