洛谷P1734 最大约数和

缺乏、安全感 2021-09-29 12:04 287阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

输入一个正整数S。

输出格式：

输出最大的约数之和。

## 输入输出样例 ##

输入样例\#1：  复制

11

输出样例\#1：  复制

9

## 说明 ##

样例说明

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

数据规模

S<=1000
    
    
    
    
    把每个物品的约数看成权值，值看做重量，做01背包

1 #include<iostream>
     2 #include<cstdio>
     3 using namespace std;
     4 const int MAXN=1001;
     5 inline char nc()
     6 {
     7     static char buf[MAXN],*p1=buf,*p2=buf;
     8     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
     9 }
    10 inline int read()
    11 {
    12     char c=nc();int x=0,f=1;
    13     while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=nc();}
    14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    15     return x*f;
    16 }
    17 inline int work(int x)
    18 {
    19     int ans=0;
    20     for(int i=1;i<x;i++)   
    21         if(x%i==0)  ans+=i;
    22     return ans;
    23 }
    24 struct node
    25 {
    26     int val,w;
    27 }a[MAXN];
    28 int dp[MAXN];
    29 int main()
    30 {
    31     #ifdef WIN32
    32     freopen("a.in","r",stdin);
    33     #else
    34     #endif
    35     int n=read();
    36     for(int i=1;i<=n;i++)   a[i].val=work(i),a[i].w=i;
    37     for(int i=1;i<=n;i++)
    38         for(int j=n;j>=a[i].w;j--)
    39             dp[j]=max(dp[j],dp[j-a[i].w]+a[i].val);
    40     printf("%d",dp[n]);
    41 }

转载于:https://www.cnblogs.com/zwfymqz/p/7911661.html

发表评论取消回复

表情：

评论列表（有 0 条评论，287人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷P1115最大子段和

洛谷P1115： https://www.luogu.com.cn/problem/P1115 本题是想求出给定序列的最大子序列和，根据题意，可以从第一个数开始遍历，每次将此

た入场券/ 2023年01月03日 04:09/ 0 赞/ 80 阅读

相关【洛谷】P1576 最小花费

前言文章来源：CSDN@LawsonAbs 合理时间：12min -------------------- 题目 [题目链接][Link 1]

骑猪看日落/ 2022年09月09日 09:12/ 0 赞/ 152 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 278 阅读

相关洛谷P1403 [AHOI2005]约数研究

题目描述科学家们在Samuel星球上的探险得到了丰富的能源储备，这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错

男娘i/ 2022年05月30日 11:27/ 0 赞/ 128 阅读

相关洛谷P1115 最大子段和

题目描述给出一段序列，选出其中连续且非空的一段使得这段和最大。输入输出格式输入格式：输入文件maxsum1.in的第一行是一个正整数N，表

电玩女神/ 2022年05月29日 10:59/ 0 赞/ 156 阅读

相关洛谷P1029 最大公约数和最小公倍数问题

题目描述输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,Q是正整数 2.要求P

短命女/ 2022年05月28日 22:23/ 0 赞/ 142 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 277 阅读

相关 [洛谷]P1121 环状最大两段子段和

[也许更好的阅读体验][Link 1] \\(\\mathcal\{Description\}\\) 给出一段环状序列，即认为\\(a\_1\\)和\\(a\_n\\)

深碍√TFBOYSˉ_/ 2021年11月16日 08:22/ 0 赞/ 277 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 398 阅读

相关洛谷P1734 最大约数和

题目描述选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。输入输出格式输入格式：输入一个正整数S。输出格式：

缺乏、安全感/ 2021年09月29日 12:04/ 0 赞/ 288 阅读