P1734 最大约数和

佚名 6年前 (2019-05-12) 随笔 1411人围观抢沙发百度已收录

题目

题目描述

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

链接

传送门

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路

还是一道比较水的题，基本的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;
}