luogu P1734 最大约数和（01 背包）

链接：https://www.luogu.org/problemnew/show/P1734

题面：

题目描述

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

输入输出格式

输入格式：

输入一个正整数S。

输出格式：

输出最大的约数之和。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

样例说明

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

数据规模

S<=1000

思路：

把这个数的因数和看成这个数的权值，那么就可以转化成一道01背包了，因为数据非常小，直接暴力预处理出每个数的因数和。

实现代码；

#include<bits/stdc++.h>

using namespace std;

const int M = 1e5+;

int a[M],dp[M],n;

void init(){

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

        for(int j = ;j < i;j ++)

            if(i%j==) a[i] += j;

}

int main()

{

    cin>>n;

    init();

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

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

            dp[j] = max(dp[j],dp[j-i]+a[i]);

        }

    }

    cout<<dp[n]<<endl;

}

巴特西

luogu P1734 最大约数和（01 背包）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

巴特西

luogu P1734 最大约数和 （01 背包）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

luogu P1734 最大约数和（01 背包）