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

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

四种类型的物品&#xff0c;每一种类型物品数量都是n&#xff0c;先要从每种类型的物品中挑选一件&#xff0c;使得最后花费总和等于1000 暴力做法10000^4 看到花费总和是1000&#xff0c;很小且固定的数字&#xff0c;肯定有玄机&#xff0c;从这里想应该是用dp&#xff0c;不…...

2023-9-3 试除法判定质数

题目链接&#xff1a;试除法判定质数 #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)

汝之观览&#xff0c;吾之幸也&#xff01; 从本文开始讲下项目中用到的一些框架和技术&#xff0c;最基本的框架使用的是SpringBoot(2.5.10)Mybatis-plus(3.5.3.2)lombok(1.18.28)knife4j(3.0.3)hutool(5.8.21),可以做到代码自动生成&#xff0c;满足最基本的增删查改。 一、新…...

RNN 单元:分析 GRU 方程与 LSTM,以及何时选择 RNN 而不是变压器

一、说明 深度学习往往感觉像是在雪山上找到自己的道路。拥有坚实的原则会让你对做出决定更有信心。我们都去过那里 在上一篇文章中&#xff0c;我们彻底介绍并检查了 LSTM 单元的各个方面。有人可能会争辩说&#xff0c;RNN方法已经过时了&#xff0c;研究它们是没有意义的。的…...

Linux音频了解

ALPHA I.MX6U 开发板支持音频&#xff0c;板上搭载了音频编解码芯片 WM8960&#xff0c;支持播放以及录音功能&#xff01; 本章将会讨论如下主题内容。 ⚫ Linux 下 ALSA 框架概述&#xff1b; ⚫ alsa-lib 库介绍&#xff1b; ⚫ alsa-lib 库移植&#xff1b; ⚫ alsa-l…...

精心整理了优秀的GitHub开源项目,包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等,空闲的时候方便看看提高自己的视野

精心整理了优秀的GitHub开源项目&#xff0c;包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等&#xff0c;空闲的时候方便看看提高自己的视野。 刚开源就变成新星的 igl&#xff0c;不仅获得了 2k star&#xff0c;也能提高你开发游戏的效率&#xff0c;摆…...

Leetcode54螺旋矩阵

思路&#xff1a;用set记录走过的地方&#xff0c;记下走的方向&#xff0c;根据方向碰壁变换 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();才能获取表格的相关信息 没解决怎么获取选中的行的行号&#xff0c;采用自己记的方式实习的。 利用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

快捷键支持&#xff1a; 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&#xff1a;海量日志收集系统【上篇——LogAgent实现】 下篇&#xff1a;Go实现LogCollect&#xff1a;海量日志收集系统【下篇——开发LogTransfer】 项目架构图&#xff1a; 0 项目背景与方案选择 背景 当公司发展的越来越大&#xff0c;业务越来越复杂…...

MySQL (1)

目录 操作须知 数据类型 1 DDL 1.1 操作库 1.2 操作表 1.3 操作字段(ALTER TABLE 表名) 2 DML 3 DQL(见下章) 操作须知 ※ MySQL在windows环境不区分大小写,但在Linux环境严格区分大小写 ※ 不同的数据库可能存在同名的表,可以给表前加"数据库前缀" //例:…...

MR混合现实汽车维修情景实训教学演示

MR混合现实技术应用于汽车维修课堂中&#xff0c;能够赋予学生更加真实&#xff0c;逼真地学习环境&#xff0c;让学生在情景体验中不断提高自己的专业能力。 MR混合现实汽车维修情景实训教学演示具体体现在&#xff1a; 1. 虚拟维修指导&#xff1a;利用MR技术&#xff0c;可…...

ChatGPT在航空航天工程和太空探索中的潜在应用如何?

ChatGPT在航空航天工程和太空探索领域具有广泛的潜在应用。这些应用可以涵盖从设计和模拟到任务控制和数据分析的多个方面。本文将探讨ChatGPT在航空航天和太空探索中的各种可能应用&#xff0c;包括设计优化、任务规划、智能导航、卫星通信、数据分析和太空探测器运行。 ### …...

算法基础第三章

算法基础第三章 1、dfs(深度搜索)1.1、 递归回溯1.2、递归剪枝&#xff08;剪枝就是判断接下来的递归都不会满足条件&#xff0c;直接回溯&#xff0c;不再继续往下无意义的递归&#xff09; 2、bfs(广度搜索)2.1、最优路径&#xff08;只适合于边权都相等的题&#xff09; 3、…...

ElementUI浅尝辄止20:Pagination 分页

分页组件常见于管理系统的列表查询页面&#xff0c;数据量巨大时需要分页的操作。 当数据量过多时&#xff0c;使用分页分解数据。 1.如何使用&#xff1f; /*设置layout&#xff0c;表示需要显示的内容&#xff0c;用逗号分隔&#xff0c;布局元素会依次显示。prev表示上一页…...

Docker从认识到实践再到底层原理(二-1)|容器技术发展史+虚拟化容器概念和简介

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...

什么是大模型?1750亿、700GB的GPT大模型大在哪?

文章目录 什么是大模型&#xff1f;1750亿、700GB的GPT大模型大在哪&#xff1f; 什么是大模型&#xff1f; 在人工智能领域&#xff0c;模型是指一种对数据进行处理和分析的数学结构。模型越复杂&#xff0c;能够处理的数据量和处理的准确性都会得到提高。 随着人工智能技术…...

剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题 和 剑指 Offer 10- I. 斐波那契数列 很像&#xff0c;改一下初始值就行了。 方法一 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…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

NFT模式:数字资产确权与链游经济系统构建

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

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...