每日一题-动态规划(从不同类型的物品中各挑选一个,使得最后花费总和等于1000)

四种类型的物品,每一种类型物品数量都是n,先要从每种类型的物品中挑选一件,使得最后花费总和等于1000
暴力做法10000^4
看到花费总和是1000,很小且固定的数字,肯定有玄机,从这里想应该是用dp,不难想到用dp[i][j]表示前i种类型的物品花费为j的方案数量,思考转移方程:
dp[i][j] = dp[i-1][j-A] * js[i][A],js[i][A]表示i类型的物件花销为A的方案数量,如此只需要枚举j和A,它们的范围就是1000以内
#include <iostream>
#include <vector>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;int dp[5][1100], js[5][11000];
int n;
vector<int> ve[5];
int main() {ios;cin >> n;for(int i = 1; i <= n; i ++) {int a, b , c, d;cin >> a >> b >> c >> d;ve[1].push_back(a);ve[2].push_back(b);ve[3].push_back(c);ve[4].push_back(d);}for(int i = 1; i <= 4; i++) {for(int j = 0; j < ve[i].size(); j++) {js[i][ve[i][j]] ++;}}for(auto p : ve[1]) {dp[1][p] ++;}for(int i = 2; i <= 4; i++) {for(int j = 1; j <= 1000; j++) {if(js[i][j]) {for(int k = j; k <= 1000; k++) {dp[i][k] += dp[i-1][k-j] * js[i][j];}}}}cout << dp[4][1000];return 0;
}
/*
3
250 250 250 250
156 201 205 400
205 190 100 250
*/
相关文章:
每日一题-动态规划(从不同类型的物品中各挑选一个,使得最后花费总和等于1000)
四种类型的物品,每一种类型物品数量都是n,先要从每种类型的物品中挑选一件,使得最后花费总和等于1000 暴力做法10000^4 看到花费总和是1000,很小且固定的数字,肯定有玄机,从这里想应该是用dp,不…...
2023-9-3 试除法判定质数
题目链接:试除法判定质数 #include <iostream>using namespace std;bool is_prime(int n) {if(n < 2) return false;for(int i 2; i < n / i; i){if(n % i 0) return false;}return true; }int main() {int n;cin >> n;while(n--){int x;cin &g…...
【Apollo学习笔记】——规划模块TASK之RULE_BASED_STOP_DECIDER
文章目录 前言RULE_BASED_STOP_DECIDER相关配置RULE_BASED_STOP_DECIDER总体流程StopOnSidePassCheckClearDoneCheckSidePassStopIsPerceptionBlockedIsClearToChangeLaneCheckSidePassStopBuildStopDecisionELSE:涉及到的一些其他函数NormalizeAngleSelfRotate CheckLaneChang…...
【SpringBoot】最基础的项目架构(SpringBoot+Mybatis-plus+lombok+knife4j+hutool)
汝之观览,吾之幸也! 从本文开始讲下项目中用到的一些框架和技术,最基本的框架使用的是SpringBoot(2.5.10)Mybatis-plus(3.5.3.2)lombok(1.18.28)knife4j(3.0.3)hutool(5.8.21),可以做到代码自动生成,满足最基本的增删查改。 一、新…...
RNN 单元:分析 GRU 方程与 LSTM,以及何时选择 RNN 而不是变压器
一、说明 深度学习往往感觉像是在雪山上找到自己的道路。拥有坚实的原则会让你对做出决定更有信心。我们都去过那里 在上一篇文章中,我们彻底介绍并检查了 LSTM 单元的各个方面。有人可能会争辩说,RNN方法已经过时了,研究它们是没有意义的。的…...
Linux音频了解
ALPHA I.MX6U 开发板支持音频,板上搭载了音频编解码芯片 WM8960,支持播放以及录音功能! 本章将会讨论如下主题内容。 ⚫ Linux 下 ALSA 框架概述; ⚫ alsa-lib 库介绍; ⚫ alsa-lib 库移植; ⚫ alsa-l…...
精心整理了优秀的GitHub开源项目,包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等,空闲的时候方便看看提高自己的视野
精心整理了优秀的GitHub开源项目,包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等,空闲的时候方便看看提高自己的视野。 刚开源就变成新星的 igl,不仅获得了 2k star,也能提高你开发游戏的效率,摆…...
Leetcode54螺旋矩阵
思路:用set记录走过的地方,记下走的方向,根据方向碰壁变换 class Solution:def spiralOrder(self, matrix: list[list[int]]) -> list[int]:max_rows len(matrix)max_cols len(matrix[0])block_nums max_cols * max_rowscount 1i 0j…...
element-plus 表格-方法、事件、属性的使用
记录element-plus 表格的使用。方法、事件、属性的使用。因为是vue3的方式用到了const install getCurrentInstance();才能获取表格的相关信息 没解决怎么获取选中的行的行号,采用自己记的方式实习的。 利用row-class-name"setRowClass"实现样式的简单…...
NVME Linux的查询命令-继续更新
NVME Linux的查询命令 查看NVMe设备 # nvme list 查看nvme controller 支持的一些特性 # nvme id-ctrl /dev/nvme0 查看设备smart log信息 # nvme smart-log /dev/nvme0 查看设备error 信息 # nvme error-log /dev/nvme0 设备的所有命名空间 # nvme list-ns /dev/nvmeX 检…...
pyqt5-自定义文本域1
快捷键支持: CTRL鼠标滚轮实现字体大小调整 支持复制当前行 剪切当前行 # 多行文本框 class TextEdit(QTextEdit):def __init__(self, parentNone):super().__init__(parent)self.setStyleSheet("background-color: #262626;color: #d0d0d0;")self.setFon…...
Go实现LogCollect:海量日志收集系统【上篇——LogAgent实现】
Go实现LogCollect:海量日志收集系统【上篇——LogAgent实现】 下篇:Go实现LogCollect:海量日志收集系统【下篇——开发LogTransfer】 项目架构图: 0 项目背景与方案选择 背景 当公司发展的越来越大,业务越来越复杂…...
MySQL (1)
目录 操作须知 数据类型 1 DDL 1.1 操作库 1.2 操作表 1.3 操作字段(ALTER TABLE 表名) 2 DML 3 DQL(见下章) 操作须知 ※ MySQL在windows环境不区分大小写,但在Linux环境严格区分大小写 ※ 不同的数据库可能存在同名的表,可以给表前加"数据库前缀" //例:…...
MR混合现实汽车维修情景实训教学演示
MR混合现实技术应用于汽车维修课堂中,能够赋予学生更加真实,逼真地学习环境,让学生在情景体验中不断提高自己的专业能力。 MR混合现实汽车维修情景实训教学演示具体体现在: 1. 虚拟维修指导:利用MR技术,可…...
ChatGPT在航空航天工程和太空探索中的潜在应用如何?
ChatGPT在航空航天工程和太空探索领域具有广泛的潜在应用。这些应用可以涵盖从设计和模拟到任务控制和数据分析的多个方面。本文将探讨ChatGPT在航空航天和太空探索中的各种可能应用,包括设计优化、任务规划、智能导航、卫星通信、数据分析和太空探测器运行。 ### …...
算法基础第三章
算法基础第三章 1、dfs(深度搜索)1.1、 递归回溯1.2、递归剪枝(剪枝就是判断接下来的递归都不会满足条件,直接回溯,不再继续往下无意义的递归) 2、bfs(广度搜索)2.1、最优路径(只适合于边权都相等的题) 3、…...
ElementUI浅尝辄止20:Pagination 分页
分页组件常见于管理系统的列表查询页面,数据量巨大时需要分页的操作。 当数据量过多时,使用分页分解数据。 1.如何使用? /*设置layout,表示需要显示的内容,用逗号分隔,布局元素会依次显示。prev表示上一页…...
Docker从认识到实践再到底层原理(二-1)|容器技术发展史+虚拟化容器概念和简介
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...
什么是大模型?1750亿、700GB的GPT大模型大在哪?
文章目录 什么是大模型?1750亿、700GB的GPT大模型大在哪? 什么是大模型? 在人工智能领域,模型是指一种对数据进行处理和分析的数学结构。模型越复杂,能够处理的数据量和处理的准确性都会得到提高。 随着人工智能技术…...
剑指 Offer 10- II. 青蛙跳台阶问题
剑指 Offer 10- II. 青蛙跳台阶问题 和 剑指 Offer 10- I. 斐波那契数列 很像,改一下初始值就行了。 方法一 class Solution {int mod (int) 1e9 7;public int numWays(int n) {if(n < 1) return 1;int[] dp new int[n 1];dp[1] 1;dp[2] 2;for(int i 3…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
