求助
查看原帖
求助
504142
micmic楼主2022/5/23 17:00
#include<iostream>
#include<math.h>
using namespace std;

int S;
int a[1005];
int f[1005]; //f[j]是优化后的二维数组,j是当前不超过j的数(类似背包问题中背包容量为j时) 

//函数功能:求一个数所有的约数之和
int Sum(int n){
	int sum=0;
	for(int i=1;i<S;i++){
		if(n%i==0)
			sum+=i;
	}
	return sum;
} 

//把1~n的数的约数和存到a数组(这里是可以用筛法优化的,没用)
void SetVal(int n){
	for(int i=1;i<=n;i++){
		a[i]=Sum(i);
	}
}
 

int main(){
	cin>>S;
	SetVal(S);
	for(int i=1;i<=S;i++)
		for(int j=S;j>=i;j--)
			f[j]=max(f[j],f[j-i]+a[i]); 
			
    cout<<f[S];
}
2022/5/23 17:00
加载中...