2126.最大约数和

input:maxsum.in output:maxsum.out

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

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

输入

输入一个正整数S

输出

输出最大的约数之和

样例输入

11

样例输出

9

数据范围限制

对于30%的数据， S<=10；
对于100%的数据， S <=1000。

提示

样例说明:
取数字4和6，可以得到最大值(1 + 2) + (1 + 2 + 3) = 9。

代码

#include<bits/stdc++.h>
using namespace std;
int s,ans=0;
int a[1000],b[1000],f[1000];
int max(int a,int b){
	return (a>b?a:b);
}
void find(int temp){
	for(int i=1;i<=temp-1;i++){
		if(temp%i==0){
			b[temp]+=i;
		}
	}
}
int main()
{
	freopen("maxsum.in","r",stdin);
	freopen("maxsum.out","w",stdout);
	scanf("%d",&s);
	ans=0;
	for(int i=1;i<=s;i++){
		find(i);
		a[i]=i;
	} 
	for(int i=1;i<=s;i++){
		for(int j=s;j>=a[i];j--){
			f[j]=max(f[j-a[i]]+b[i],f[j]);
		}
	}
	printf("%d",f[s]);
}