当前位置: 首页 > news >正文

洛谷 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 的若干个不同的正整数&#xff0c;使得所有数的约数&#xff08;不含它本身&#xff09;之和最大。 输入格式 输入一个正整数 S。 输出格式 输出最大的约数之和。 输入输出样例 输入 #1复制 …...

Golang 执行流程分析

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

python学opencv|读取图像(五十一)使用修改图像像素点上BGR值实现图像覆盖效果

【1】引言 前序学习了图像的得加方法&#xff0c;包括使用add()函数直接叠加BGR值、使用bitwise()函数对BGR值进行按位计算叠加和使用addWeighted()函数实现图像加权叠加至少三种方法。文章链接包括且不限于&#xff1a; python学opencv|读取图像&#xff08;四十二&#xff…...

Flask数据的增删改查(CRUD)_flask删除数据自动更新

查询年龄小于17的学生信息 Student.query.filter(Student.s_age < 17) students Student.query.filter(Student.s_age.__lt__(17))模糊查询&#xff0c;使用like&#xff0c;查询姓名中第二位为花的学生信息 like ‘_花%’,_代表必须有一个数据&#xff0c;%任何数据 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 …...

数据库对象

数据库对象 数据库对象是构成数据库结构的基本单位&#xff0c;它们定义了数据库存储的数据类型、数据的组织方式以及数据之间的关系。在数据库中&#xff0c;对象可以包括表&#xff0c;视图&#xff0c;索引&#xff0c;触发器&#xff0c;存储过程&#xff0c;函数等多种类…...

EtherCAT主站IGH-- 27 -- IGH之globals.h文件解析

EtherCAT主站IGH-- 27 -- IGH之globals.h文件解析 0 预览一 该文件功能宏定义数据结构打印宏三 h文件翻译四 c文件翻译该文档修改记录:总结0 预览 一 该文件功能 该文件包含了一些全局定义和宏,用于 IgH EtherCAT 主站(EtherCAT Master)的实现。包括了一些超时设定、宏定义…...

2025多目标优化创新路径汇总

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

15JavaWeb——Maven高级篇

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

使用Ollama本地化部署DeepSeek

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

蓝桥杯刷题DAY1:前缀和

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

【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户注册

&#x1f9f8;安清h&#xff1a;个人主页 &#x1f3a5;个人专栏&#xff1a;【计算机网络】【Mybatis篇】 &#x1f6a6;作者简介&#xff1a;一个有趣爱睡觉的intp&#xff0c;期待和更多人分享自己所学知识的真诚大学生。 目录 &#x1f3af;项目基本介绍 &#x1f6a6;项…...

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)

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

Baklib揭示内容中台实施最佳实践的策略与实战经验

内容概要 在当前数字化转型的浪潮中&#xff0c;内容中台的概念日益受到关注。它不再仅仅是一个内容管理系统&#xff0c;而是企业提升运营效率与灵活应对市场变化的重要支撑平台。内容中台的实施离不开最佳实践的指导&#xff0c;这些实践为企业在建设高效内容中台时提供了宝…...

C++11新特性之lambda表达式

1.介绍 C11引入了lambda表达式。lambda表达式提供一种简洁的方式来定义匿名函数对象&#xff0c;使得在需要临时定义一个函数时非常方便。 2.lambda表达式用法 lambda表达式的基本用法为&#xff1a; [捕获列表]&#xff08;参数列表&#xff09;->返回类型 { 函数体 …...

洛谷 P10289 [GESP样题 八级] 小杨的旅游 C++ 完整题解

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

使用 Tauri 2 + Next.js 开发跨平台桌面应用实践:Singbox GUI 实践

Singbox GUI 实践 最近用 Tauri Next.js 做了个项目 - Singbox GUI&#xff0c;是个给 sing-box 用的图形界面工具。支持 Windows、Linux 和 macOS。作为第一次接触这两个框架的新手&#xff0c;感觉收获还蛮多的&#xff0c;今天来分享下开发过程中的一些经验~ 为啥要做这个…...

JWT入门

一、初识JWT&#xff1a;新时代的身份认证方案 在分布式系统成为主流的今天&#xff0c;传统的Session认证方式逐渐显露出局限性。JWT&#xff08;JSON Web Token&#xff09;作为现代Web开发的认证新标准&#xff0c;凭借其无状态、跨域友好和安全性等特性&#xff0c;正在成为…...

Python - Quantstats量化投资策略绩效统计包 - 详解

使用Quantstats包做量化投资绩效统计的时候因为Pandas、Quantstats版本不匹配踩了一些坑&#xff1b;另外&#xff0c;Quantstats中的绩效统计指标非常全面&#xff0c;因此详细记录一下BUG修复方法、使用说明以及部分指标的内涵示意。 一、Quantstats安装及版本匹配问题 可以…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...