专栏首页数据结构与算法洛谷P1734 最大约数和

洛谷P1734 最大约数和

题目描述

选取和不超过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 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #490 (Div. 3)

    attack
  • 洛谷P2765 魔术球问题(贪心 最大流)

    attack
  • HDU4576 Robot(概率)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack
  • HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444

    Ch_Zaqdt
  • Codeforces Round #535 (Div. 3) B. Divisors of Two Integers(思维)

    题目链接:http://codeforces.com/contest/1108/problem/B

    Ch_Zaqdt
  • AGC015 C Nuske vs Phantom Thnook(前缀和)

    attack
  • 2017.5.26暴力赛解题报告

    预计分数:T1:40AC+60TLE      T2:40AC+60TLE        T3:10AC+90TLE      总分=90 实际分数:T1:10...

    attack
  • P1631 序列合并

    题目描述 有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到 个和,求这 个和中最小的N个。 输入输出格式 输入格式: 第一行一个正整数N; 第...

    attack
  • 洛谷P2765 魔术球问题(贪心 最大流)

    attack
  • P1018 乘积最大

    题目描述 今年是国际数学联盟确定的“2000――世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智...

    attack

扫码关注云+社区

领取腾讯云代金券