落谷 P1734 最大约数和
2024-09-06 07:02:17
题目描述
选取和不超过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 ;
}
反思::遇到背包问题时有,一定要仔细考虑谁是价值谁知体积。
最新文章
- Oracle 把秒转成时分秒格式(hh24:mm:ss);检测字符串是否是数字;字符串转换为数字
- js压缩图片base64长度
- 快速学习C语言一: Hello World
- POJ 2402 Palindrome Numbers
- jfinal 基本应用 --事务回滚
- Centos7 安装 Nginx
- weblogic日志小结
- [cocoapods]cocoapods问题解决
- hdu4433 locker
- UDP打洞和心跳包设计
- 洛谷 P3379 【模板】最近公共祖先(LCA)Tarjan离线
- babel版本兼容报错处理:Plugin/Preset files are not allowed to export objects
- jquery动态设置图片路径和超链接href属性
- WPF设计界面不执行代码
- GZip、deflate和sdch压缩(网摘整理)
- ios 11越狱移除
- CentOS6.5安装sqlite3
- ZooKeeper 集群环境搭建 (本机3个节点)
- 中国大学MOOC 玩转AutoCAD 熟悉AutoCAD的工作空间
- 浅谈React虚拟DOM