题目描述

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

输入格式

输入一个正整数S。

输出格式

输出最大的约数之和。

输入输出样例

输入 #1复制

11
输出 #1复制

9

说明/提示

样例说明

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

数据规模

S<=1000

第一眼看到这个题目的有点蒙,,没思路,,百度了一下,,,原来这么简单。
思路:简单的01背包问题,先构造一个数组里面存有每个数x的约数和,然后约束和为价值,,对应的数字为体积,,总数s为背包容积,,,简单01背包问题。。唉!!
#include<iostream>
using namespace std;
typedef long long ll;
ll arr[+];
ll dp[+];
ll ysh(int x){
int sum=;
for(int i=;i<x;i++){
if(x%i==) sum+=i;
}
return sum;
}
int main(){
int s;
cin>>s;
for(int i=;i<s;i++){
arr[i]=ysh(i);
}
for(int i=;i<s;i++)
for(int j=s;j>=i;j--)
dp[j]=max(dp[j],dp[j-i]+arr[i]);
cout<<dp[s]<<endl;
return ;
}
反思::遇到背包问题时有,一定要仔细考虑谁是价值谁知体积。

最新文章

  1. Oracle 把秒转成时分秒格式(hh24:mm:ss);检测字符串是否是数字;字符串转换为数字
  2. js压缩图片base64长度
  3. 快速学习C语言一: Hello World
  4. POJ 2402 Palindrome Numbers
  5. jfinal 基本应用 --事务回滚
  6. Centos7 安装 Nginx
  7. weblogic日志小结
  8. [cocoapods]cocoapods问题解决
  9. hdu4433 locker
  10. UDP打洞和心跳包设计
  11. 洛谷 P3379 【模板】最近公共祖先(LCA)Tarjan离线
  12. babel版本兼容报错处理:Plugin/Preset files are not allowed to export objects
  13. jquery动态设置图片路径和超链接href属性
  14. WPF设计界面不执行代码
  15. GZip、deflate和sdch压缩(网摘整理)
  16. ios 11越狱移除
  17. CentOS6.5安装sqlite3
  18. ZooKeeper 集群环境搭建 (本机3个节点)
  19. 中国大学MOOC 玩转AutoCAD 熟悉AutoCAD的工作空间
  20. 浅谈React虚拟DOM

热门文章

  1. Android适配器
  2. Thinking in Java学习杂记(第7章)
  3. 2020年Java多线程与并发系列22道高频面试题(附思维导图和答案解析)
  4. PTA | 1014 福尔摩斯的约会 (20分)
  5. 【WPF学习】第六十六章 支持可视化状态
  6. Redis系列(五):Redis的过期键删除策略
  7. 【php】日期时间
  8. 如何在Vue中优雅的使用防抖节流
  9. mybatis源码分析:启动过程
  10. Kafka,RocketMQ,RabbitMQ部署与使用体验