题目描述

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

												

最新文章

  1. [ORACLE错误]oracle 不能更新 PL/SQL 点击“edit data”报“ these query results are not updateable”
  2. Stakeholder Risk Management
  3. 常用SQL操作(MySQL或PostgreSQL)与相关数据库概念
  4. ubuntu下读取数据库中文乱码解决
  5. Android Gradle实用技巧——APK文件名中加上SVN版本号,日期等
  6. 图形化Cisco设备管理实践(附安装配置视频)
  7. ajax实现md5加密
  8. Networking - IPv4 报文格式
  9. Xml通用操作类
  10. git日常操作
  11. sublime使用方法
  12. Unbutu14.04 启用 root 并禁用guest
  13. 智能指针剖析(上)std::auto_ptr与boost::scoped_ptr
  14. 《精通Linux C编程》1.3Linux系统的常用命令-笔记
  15. 函数声明 和 var声明的优先级
  16. Python下Tesseract Ocr引擎及安装介绍
  17. Impacket官方使用指南
  18. react-native开源组件react-native-wechat学习
  19. nignx reload的时候报错invalid PID number
  20. TSQL--游标Dem

热门文章

  1. silverlight RadGridView 动态添加数据列
  2. OS__信号量(semaphore)PV操作
  3. web.xml报错Cannot resolve class &#39;StrutsPrepareAndExecuteFilter&#39; (idea创建SSH项目)
  4. CCF 201509-2 日期计算 (水题)
  5. 给source insight添加.cc的C++文件后缀识别(转载)
  6. DOM学习笔记(三)DOM元素的访问、修改与事件
  7. java多线程知识点收集-总
  8. VR相关学习资源
  9. 如何使Label有修改功能
  10. IT兄弟连 JavaWeb教程 JSP内置对象2