每日一题-动态规划(从不同类型的物品中各挑选一个,使得最后花费总和等于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…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
