【洛谷】【动态规划/01背包】P1734 最大约数和

【题目描述：】

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

【输入格式：】

输入一个正整数S。

【输出格式：】

输出最大的约数之和。

[算法分析：]

01背包，每个数的约数和为其价值，数的大小为其花费

注意1的价值应该为0

[Code:]

#include<iostream>

#include<cstdio>

using namespace std;

int n, v[1001], f[1001];

int work(int x) {

	if(x == 1) return 0;

	int l = x/2, ret = 1;

	for(int i=2; i<=l; ++i)

		if(x % i == 0) ret += i;

	return ret;

}

int main() {

	cin >> n;

	for(int i=1; i<=n; ++i) v[i] = work(i);

	for(int i=1; i<=n; ++i)

		for(int j=n; j>=i; --j)

			f[j] = max(f[j], f[j-i]+v[i]);

	cout << f[n];

}

巴特西

【洛谷】【动态规划/01背包】P1734 最大约数和

[算法分析：]

[Code:]

最新文章

热门文章