题目描述:
选取和不超过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; }