洛谷 P1734 最大约数和
2024-09-08 01:25:40
题目描述
选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。
输入输出格式
输入格式:
输入一个正整数S。
输出格式:
输出最大的约数之和。
输入输出样例
输入样例#1:
11
输出样例#1:
9
说明
样例说明
取数字4和6,可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000
背包dp
dp入门中。。
屠龙宝刀点击就送
#include <cstdio>
#include <cmath>
int dp[],s[],l;
void init()
{
for(int sum=,i=;i<=;i++,sum=)
{
for(int j=;j<=sqrt(i);j++)
{
if(i%j==)
{
sum+=j;
if(j!=i/j) sum+=i/j;
}
}
s[i]=sum;
}
s[]=;
}
int max(int a,int b) {return a>b?a:b;}
int main()
{
init();
scanf("%d",&l);
for(int i=;i<=l;i++)
for(int j=l;j>=i;j--)
dp[j]=max(dp[j-i]+s[i],dp[j]);
printf("%d\n",dp[l]);
return ;
}
最新文章
- [ORACLE错误]oracle 不能更新 PL/SQL 点击“edit data”报“ these query results are not updateable”
- Stakeholder Risk Management
- 常用SQL操作(MySQL或PostgreSQL)与相关数据库概念
- ubuntu下读取数据库中文乱码解决
- Android Gradle实用技巧——APK文件名中加上SVN版本号,日期等
- 图形化Cisco设备管理实践(附安装配置视频)
- ajax实现md5加密
- Networking - IPv4 报文格式
- Xml通用操作类
- git日常操作
- sublime使用方法
- Unbutu14.04 启用 root 并禁用guest
- 智能指针剖析(上)std::auto_ptr与boost::scoped_ptr
- 《精通Linux C编程》1.3Linux系统的常用命令-笔记
- 函数声明 和 var声明的优先级
- Python下Tesseract Ocr引擎及安装介绍
- Impacket官方使用指南
- react-native开源组件react-native-wechat学习
- nignx reload的时候报错invalid PID number
- TSQL--游标Dem
热门文章
- silverlight RadGridView 动态添加数据列
- OS__信号量(semaphore)PV操作
- web.xml报错Cannot resolve class &#39;StrutsPrepareAndExecuteFilter&#39; (idea创建SSH项目)
- CCF 201509-2	日期计算 (水题)
- 给source insight添加.cc的C++文件后缀识别(转载)
- DOM学习笔记(三)DOM元素的访问、修改与事件
- java多线程知识点收集-总
- VR相关学习资源
- 如何使Label有修改功能
- IT兄弟连 JavaWeb教程 JSP内置对象2