P1734 最大约数和

题目

题目描述

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

链接

传送门

思路

还是一道比较水的题，基本的01背包思想，注意找出与01背包的联系（只不过多了一步寻找约数和的过程）注意求约数和不循环到该数本身

把i本身当体积，把约数和当价值

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}
int s;
int calc(int x) {
	int ans=0;
	for(int i=1; i<x; ++i) { //注意不包括x本身
		if(x%i==0) {
			ans+=i;
		}
	}
	return ans;
}
int f[100000],a[100000];
int main() {
	cin>>s;
	for(int i=1; i<=s; ++i) {
		a[i]=calc(i);
	}
	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];
	return 0;
}