洛谷 P1734 最大约数和 C语言
P1734 最大约数和 - 洛谷 | 计算机科学教育新生态
题目描述
选取和不超过 S 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
输入 #1复制
11
输出 #1复制
9
说明/提示
【样例说明】
取数字 4 和 6,可以得到最大值 (1+2)+(1+2+3)=9。
【数据规模】
对于 100% 的数据,1≤S≤1000。
思路:
题目的意思是选取诺干个数,这些数之和小于n,求出这些数的约数最大和。
我们预处理把每个数的约数写出来。然后就是背包问题了。
注意只有dp会满分
代码如下:
暴力:
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const ll N = 2001;
ll cnt[N];
ll num[N];
ll n;
int is_number(ll x)
{int sum = 0;for(ll i = 1 ; i < x ; i++){if(x % i == 0)sum += i;}return sum;
}
ll dfs(ll x,ll sp)
{if(x > n-1)return 0;if(sp >= num[x])return max(dfs(x+1,sp-num[x])+cnt[x],dfs(x+1,sp));elsereturn dfs(x+1,sp);}int main()
{cin >> n;for(ll i = 1 ; i <= n-1 ; i++){cnt[i] += is_number(i);//求出1~n-1的各个约数之和
// cout << i << "的约数之和:" << arr[i] << endl;num[i] = i; }cout << dfs(1,n);return 0;}
记忆化搜索:
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const ll N = 2001;
ll cnt[N];
ll num[N];
ll n;
ll mem[N][N];
int is_number(ll x)
{int sum = 0;for(ll i = 1 ; i < x ; i++){if(x % i == 0)sum += i;}return sum;
}
ll dfs(ll x,ll sp)
{ll sum = -1e9;if(mem[x][sp])return mem[x][sp];if(sp <= 0)return 0;if(x > n-1)return 0;if(sp >= num[x])sum = max(dfs(x+1,sp-num[x]) + cnt[x],dfs(x+1,sp));elsesum = dfs(x+1,sp);mem[x][sp] = sum;return sum;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(ll i = 1 ; i < n ; i++){cnt[i] += is_number(i);//求出1~n-1的各个约数之和
// cout << i << "的约数之和:" << arr[i] << endl;num[i] = i; }cout << dfs(1,n);return 0;}
dp:
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const ll N = 2001;
ll cnt[N];
ll num[N];
ll n;
ll f[N][N];
int is_number(ll x)
{int sum = 0;for(ll i = 1 ; i < x ; i++){if(x % i == 0)sum += i;}return sum;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(ll i = 1 ; i < n ; i++){cnt[i] += is_number(i);//求出1~n-1的各个约数之和
// cout << i << "的约数之和:" << arr[i] << endl;num[i] = i; }for(ll i = n-1 ; i >= 1 ; i--){for(ll j = 0 ; j <= n ; j++){if(j >= num[i])f[i][j] = max(f[i+1][j-num[i]] + cnt[i],f[i+1][j]);elsef[i][j] = f[i+1][j]; } }cout << f[1][n];return 0;}
相关文章:

洛谷 P1734 最大约数和 C语言
P1734 最大约数和 - 洛谷 | 计算机科学教育新生态 题目描述 选取和不超过 S 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入格式 输入一个正整数 S。 输出格式 输出最大的约数之和。 输入输出样例 输入 #1复制 …...

Golang 执行流程分析
文章目录 1. 编译和运行2. 编译和运行说明 1. 编译和运行 如果是对源码编译后,再执行,Go的执行流程如下图 如果我们是对源码直接 执行 go run 源码,Go的执行流程如下图 两种执行流程的方式区别 如果先编译生成了可执行文件,那么…...

python学opencv|读取图像(五十一)使用修改图像像素点上BGR值实现图像覆盖效果
【1】引言 前序学习了图像的得加方法,包括使用add()函数直接叠加BGR值、使用bitwise()函数对BGR值进行按位计算叠加和使用addWeighted()函数实现图像加权叠加至少三种方法。文章链接包括且不限于: python学opencv|读取图像(四十二ÿ…...
Flask数据的增删改查(CRUD)_flask删除数据自动更新
查询年龄小于17的学生信息 Student.query.filter(Student.s_age < 17) students Student.query.filter(Student.s_age.__lt__(17))模糊查询,使用like,查询姓名中第二位为花的学生信息 like ‘_花%’,_代表必须有一个数据,%任何数据 st…...
kamailio-ACC模块介绍【kamailio6.0. X】
Acc 模块 作者 Jiri Kuthan iptel.org jiriiptel.org Bogdan-Andrei Iancu Voice Sistem SRL bogdanvoice-system.ro Ramona-Elena Modroiu rosdev.ro ramonarosdev.ro 编辑 Bogdan-Andrei Iancu Voice Sistem SRL bogdanvoice-system.ro Sven Knoblich 1&1 Internet …...
数据库对象
数据库对象 数据库对象是构成数据库结构的基本单位,它们定义了数据库存储的数据类型、数据的组织方式以及数据之间的关系。在数据库中,对象可以包括表,视图,索引,触发器,存储过程,函数等多种类…...
EtherCAT主站IGH-- 27 -- IGH之globals.h文件解析
EtherCAT主站IGH-- 27 -- IGH之globals.h文件解析 0 预览一 该文件功能宏定义数据结构打印宏三 h文件翻译四 c文件翻译该文档修改记录:总结0 预览 一 该文件功能 该文件包含了一些全局定义和宏,用于 IgH EtherCAT 主站(EtherCAT Master)的实现。包括了一些超时设定、宏定义…...

2025多目标优化创新路径汇总
多目标优化是当下非常热门且有前景的方向!作为AI领域的核心技术之一,其专注于解决多个相互冲突的目标的协同优化问题,核心理念是寻找一组“不完美但均衡”的“帕累托最优解”。在实际中,几乎处处都有它的身影。 但随着需求场景的…...

15JavaWeb——Maven高级篇
Maven高级 Web开发讲解完毕之后,我们再来学习Maven高级。其实在前面的课程当中,我们已经学习了Maven。 我们讲到 Maven 是一款构建和管理 Java 项目的工具。经过前面 10 多天 web 开发的学习,相信大家对于 Maven 这款工具的基本使用应该没什…...

使用Ollama本地化部署DeepSeek
1、Ollama 简介 Ollama 是一个开源的本地化大模型部署工具,旨在简化大型语言模型(LLM)的安装、运行和管理。它支持多种模型架构,并提供与 OpenAI 兼容的 API 接口,适合开发者和企业快速搭建私有化 AI 服务。 Ollama …...

蓝桥杯刷题DAY1:前缀和
所谓刷题,讲究的就是细心 帕鲁服务器崩坏【算法赛】 “那个帕鲁我已经观察你很久了,我对你是有些失望的,进了这个营地,不是把事情做好就可以的,你需要有体系化思考的能力。” 《幻兽帕鲁》火遍全网,成为…...

【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户注册
🧸安清h:个人主页 🎥个人专栏:【计算机网络】【Mybatis篇】 🚦作者简介:一个有趣爱睡觉的intp,期待和更多人分享自己所学知识的真诚大学生。 目录 🎯项目基本介绍 🚦项…...

MINIRAG: TOWARDS EXTREMELY SIMPLE RETRIEVAL-AUGMENTED GENERATION论文翻译
感谢阅读 注意不含评估以后的翻译原论文地址标题以及摘要介绍部分MiniRAG 框架2.1 HETEROGENEOUS GRAPH INDEXING WITH SMALL LANGUAGE MODELS2.2 LIGHTWEIGHT GRAPH-BASED KNOWLEDGE RETRIEVAL2.2.1 QUERY SEMANTIC MAPPING2.2.2 TOPOLOGY-ENHANCED GRAPH RETRIEVAL 注意不含评…...

微服务入门(go)
微服务入门(go) 和单体服务对比:里面的服务仅仅用于某个特定的业务 一、领域驱动设计(DDD) 基本概念 领域和子域 领域:有范围的界限(边界) 子域:划分的小范围 核心域…...

Baklib揭示内容中台实施最佳实践的策略与实战经验
内容概要 在当前数字化转型的浪潮中,内容中台的概念日益受到关注。它不再仅仅是一个内容管理系统,而是企业提升运营效率与灵活应对市场变化的重要支撑平台。内容中台的实施离不开最佳实践的指导,这些实践为企业在建设高效内容中台时提供了宝…...
C++11新特性之lambda表达式
1.介绍 C11引入了lambda表达式。lambda表达式提供一种简洁的方式来定义匿名函数对象,使得在需要临时定义一个函数时非常方便。 2.lambda表达式用法 lambda表达式的基本用法为: [捕获列表](参数列表)->返回类型 { 函数体 …...

洛谷 P10289 [GESP样题 八级] 小杨的旅游 C++ 完整题解
一、题目链接 P10289 [GESP样题 八级] 小杨的旅游 - 洛谷 二、题目大意 n个节点之间有n - 1条边,其中k个节点是传送门,任意两个传送门之间可以 以0单位地时间相互到达。问从u到v至少需要多少时间? 三、解题思路 输入不必多讲。 cin >> …...

使用 Tauri 2 + Next.js 开发跨平台桌面应用实践:Singbox GUI 实践
Singbox GUI 实践 最近用 Tauri Next.js 做了个项目 - Singbox GUI,是个给 sing-box 用的图形界面工具。支持 Windows、Linux 和 macOS。作为第一次接触这两个框架的新手,感觉收获还蛮多的,今天来分享下开发过程中的一些经验~ 为啥要做这个…...
JWT入门
一、初识JWT:新时代的身份认证方案 在分布式系统成为主流的今天,传统的Session认证方式逐渐显露出局限性。JWT(JSON Web Token)作为现代Web开发的认证新标准,凭借其无状态、跨域友好和安全性等特性,正在成为…...

Python - Quantstats量化投资策略绩效统计包 - 详解
使用Quantstats包做量化投资绩效统计的时候因为Pandas、Quantstats版本不匹配踩了一些坑;另外,Quantstats中的绩效统计指标非常全面,因此详细记录一下BUG修复方法、使用说明以及部分指标的内涵示意。 一、Quantstats安装及版本匹配问题 可以…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...