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

P1064 [NOIP2006 提高组] 金明的预算方案

[NOIP2006 提高组] 金明的预算方案

题目描述

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 n n n 元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

主件附件
电脑打印机,扫描仪
书柜图书
书桌台灯,文具
工作椅

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 0 0 个、 1 1 1 个或 2 2 2 个附件。每个附件对应一个主件,附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 n n n 元。于是,他把每件物品规定了一个重要度,分为 5 5 5 等:用整数 1 ∼ 5 1 \sim 5 15 表示,第 5 5 5 等最重要。他还从因特网上查到了每件物品的价格(都是 10 10 10 元的整数倍)。他希望在不超过 n n n 元的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第 j j j 件物品的价格为 v j v_j vj,重要度为 w j w_j wj,共选中了 k k k 件物品,编号依次为 j 1 , j 2 , … , j k j_1,j_2,\dots,j_k j1,j2,,jk,则所求的总和为:

v j 1 × w j 1 + v j 2 × w j 2 + ⋯ + v j k × w j k v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k} vj1×wj1+vj2×wj2++vjk×wjk

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数,分别表示总钱数 n n n 和希望购买的物品个数 m m m

2 2 2 到第 ( m + 1 ) (m + 1) (m+1) 行,每行三个整数,第 ( i + 1 ) (i + 1) (i+1) 行的整数 v i v_i vi p i p_i pi q i q_i qi 分别表示第 i i i 件物品的价格、重要度以及它对应的的主件。如果 q i = 0 q_i=0 qi=0,表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出 #1

2200

提示

数据规模与约定

对于全部的测试点,保证 1 ≤ n ≤ 3.2 × 1 0 4 1 \leq n \leq 3.2 \times 10^4 1n3.2×104 1 ≤ m ≤ 60 1 \leq m \leq 60 1m60 0 ≤ v i ≤ 1 0 4 0 \leq v_i \leq 10^4 0vi104 1 ≤ p i ≤ 5 1 \leq p_i \leq 5 1pi5 0 ≤ q i ≤ m 0 \leq q_i \leq m 0qim,答案不超过 2 × 1 0 5 2 \times 10^5 2×105

NOIP 2006 提高组 第二题

这道题其实是一个背包问题和一个正常的dp转换问题,其实不难思考

首先我们可以想到在挑选一个主件时,可能会有四种情况:
情况1:只选主件
那么此时的状态转移方程就是
d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] ] + v [ i ] ) ; dp[j]=max(dp[j],dp[j-w[i]]+v[i]); dp[j]=max(dp[j],dp[jw[i]]+v[i]);
情况2:只选主件和附件1
则可得到
d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] − f j w [ i ] [ 1 ] ] + v [ i ] + f j v [ i ] [ 1 ] ) ; dp[j]=max(dp[j],dp[j-w[i]-fjw[i][1]]+v[i]+fjv[i][1]); dp[j]=max(dp[j],dp[jw[i]fjw[i][1]]+v[i]+fjv[i][1]);
同样还有两种情况,会有以下的两种状态转移方程
d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] − f j w [ i ] [ 2 ] ] + v [ i ] + f j v [ i ] [ 2 ] ) ; dp[j]=max(dp[j],dp[j-w[i]-fjw[i][2]]+v[i]+fjv[i][2]); dp[j]=max(dp[j],dp[jw[i]fjw[i][2]]+v[i]+fjv[i][2]);
d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] − f j w [ i ] [ 1 ] − f j w [ i ] [ 2 ] ] + v [ i ] + f j v [ i ] [ 1 ] + f j v [ i ] [ 2 ] ) ; dp[j]=max(dp[j],dp[j-w[i]-fjw[i][1]-fjw[i][2]]+v[i]+fjv[i][1]+fjv[i][2]); dp[j]=max(dp[j],dp[jw[i]fjw[i][1]fjw[i][2]]+v[i]+fjv[i][1]+fjv[i][2]);

既然有了此,那么程序就好写了

#include <bits/stdc++.h>
using namespace std;int n,m;
int v[32100],w[32100],fjw[32100][3],fjv[32100][3];//v为主件的价值,w为主件的重量,fjw为附件的重量,fjv为附件的价值
int dp[33300];
int main() {cin>>n>>m;for (int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;if (c==0){v[i]=a*b;w[i]=a;}else {fjw[c][0]++;fjw[c][fjw[c][0]]=a;fjv[c][fjw[c][0]]=a*b;}}for (int i=1;i<=m;i++){for (int j=n;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//情况1只要主件if (j>=w[i]+fjw[i][1])dp[j]=max(dp[j],dp[j-w[i]-fjw[i][1]]+v[i]+fjv[i][1]);//情况2只要主件和附件1if (j>=w[i]+fjw[i][2])dp[j]=max(dp[j],dp[j-w[i]-fjw[i][2]]+v[i]+fjv[i][2]);//情况2只要主件和附件2if (j>=w[i]+fjw[i][1]+fjw[i][2])dp[j]=max(dp[j],dp[j-w[i]-fjw[i][1]-fjw[i][2]]+v[i]+fjv[i][1]+fjv[i][2]);//情况3都要}}cout<<dp[n];return 0;
}

相关文章:

P1064 [NOIP2006 提高组] 金明的预算方案

[NOIP2006 提高组] 金明的预算方案 题目描述 金明今天很开心&#xff0c;家里购置的新房就要领钥匙了&#xff0c;新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是&#xff0c;妈妈昨天对他说&#xff1a;“你的房间需要购买哪些物品&#xff0c;怎么布置&#xff0…...

大型企业组网如何规划网络

大型企业组网是一个复杂的过程&#xff0c;它需要细致的规划和设计&#xff0c;以确保网络能够满足企业的业务需求&#xff0c;同时保证性能、安全性和可扩展性。以下是规划大型企业网络的一些关键步骤和考虑因素&#xff1a; 1. 需求分析 业务需求&#xff1a;与各个业务部门…...

java:aocache的单实例缓存(二)

之前一篇博客《java:aocache的单实例缓存》介绍了aoocache使用注解AoCacheable实现单实例缓存的方式&#xff0c;同时也指出了这种方式的使用限制&#xff0c;就是这个注解定义的构造方法&#xff0c;不能再创建出新实例。 为了更灵活方便的实现单实例。aocache最新版本0.4.0增…...

ElasticSearch安装部署

简介 Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;用于实时地存储、检索和分析大数据量。它基于 Apache Lucene 搜索引擎库构建而成&#xff0c;提供了一个强大、稳定且易于扩展的搜索解决方案。 主要特点和用途&#xff1a; 分布式存储和搜索&#xff1a; E…...

数据赋能(132)——开发:数据转换——影响因素、直接作用、主要特征

影响因素 数据转换过程中需要考虑的一些影响因素&#xff1a; 数据格式与结构&#xff1a; 不同系统或应用可能使用不同的数据格式&#xff08;如JSON、XML、CSV等&#xff09;和数据结构&#xff08;如关系型数据库、非关系型数据库等&#xff09;。数据转换需要确保原始数据…...

TMGM:ASIC撤销禁令,TMGM强化合规、重启差价合约服务

TMGM作为差价合约&#xff08;CFDs&#xff09;与保证金外汇交易领域的领航者&#xff0c;安全、合规、高效被奉为我集团的终身使命。澳大利亚证券和投资委员会&#xff08;ASIC&#xff09;已正式撤销了早前针对TMGM差价合约业务实施的临时止损令。这一误会的解除&#xff0c;…...

基于SpringBoot网吧管理系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; Java精品实战案例《600套》 2025-2026年最值得选择的Java毕业设计选题大全&#xff1…...

实测2024年最佳的三款Socks5代理IP网站

一、引言 在浩瀚的网络世界中&#xff0c;Socks5代理IP服务如同导航灯塔&#xff0c;指引我们穿越数据海洋&#xff0c;安全、稳定地访问目标网站。作为专业的测评团队&#xff0c;我们深知一款优秀的Socks5代理IP网站需要具备哪些特质&#xff1a;稳定的IP资源、高效的连接速…...

Pythonnet能导入clr,但无法引入System模块?

【pythonnet详解】—— Python 和 .NET 互操作的库_pythonnet 详细使用-CSDN博客 Python中动态调用C#的dll动态链接库中方法_python 如何调用c# dll-CSDN博客 需求&#xff1a;Python调用并传List<float>类型参数给.Net 起初&#xff1a;直接 # 创建一个Python浮点数…...

媒体宣发套餐的概述及推广方法-华媒舍

在今天的数字化时代&#xff0c;对于产品和服务的宣传已经变得不可或缺。媒体宣发套餐作为一种高效的宣传方式&#xff0c;在帮助企业塑造品牌形象、扩大影响力方面扮演着重要角色。本文将揭秘媒体宣发套餐&#xff0c;为您呈现一条通往成功的路。 1. 媒体宣发套餐的概述 媒体…...

Windows和Linux C++判断磁盘空间是否充足

基本是由百度Ai写代码生成的&#xff0c;记录一下。实现此功能需要调用系统的API函数。 对于Windows&#xff0c;可调用函数GetDiskFreeSpaceEx&#xff0c;使用该函数需要包含头文件windows.h。该函数的原型&#xff1a; 它的四个参数&#xff1a; lpDirectoryName&#xff0…...

数据访问层如何提取数据到其他层,其他类中

当然可以&#xff0c;以下是一些具体的例子&#xff0c;展示了如何将数据库访问逻辑封装在一个单独的类中&#xff0c;并在其他类中使用这个类来获取数据。 数据库访问类&#xff08;DatabaseAccess.java&#xff09;&#xff1a; java复制代码 import java.sql.*; import ja…...

【JS】AI总结:JavaScript中常用的判空方法

在JavaScript中&#xff0c;判空是一个常见的操作&#xff0c;因为变量可能未定义、未初始化或包含特定的空值。以下是JavaScript中常用的判空方法&#xff1a; 使用if语句直接判断&#xff1a; 如果变量是null、undefined、0、NaN、空字符串&#xff08;""&#xff…...

Rust单元测试、集成测试

单元测试、集成测试 在了解了如何在 Rust 中写测试用例后&#xff0c;本章节我们将学习如何实现单元测试、集成测试&#xff0c;其实它们用到的技术还是上一章节中的测试技术&#xff0c;只不过对如何组织测试代码提出了新的要求。 单元测试 单元测试目标是测试某一个代码单…...

vue全局方法plugins/utils

一、在src目录下创建一个plugins文件夹 test.ts文件存放创建的方法&#xff0c;index.ts用于接收所有自定义方法进行统一处理 二、编写自定义方法 // test.ts文件 export default {handleTest(val1: number, val2: number) {// 只是一个求和的方法return val1 val2;}, };三…...

高阶算法班从入门到精通之路

课程介绍 本课程旨在帮助学员深入理解算法与数据结构的核心概念&#xff0c;从而掌握高级算法设计与分析技能。每集课程内容精心设计&#xff0c;涵盖了常用数据结构、经典算法及其应用场景等方面的深度讲解&#xff0c;同时通过大量实例演练&#xff0c;帮助学员提升解决实际…...

C++ 左值右值

文章目录 概述左值右值右值引用左值和右值的互换 小结 概述 左值和右值属于2中不同的表达式类型&#xff1b;它们在表达式中扮演不同的角色&#xff0c;特别是在赋值操作和函数参数传递中。 左值 定义&#xff1a;左值是指那些在内存中有确定位置的表达式&#xff0c;可以出…...

[数据集][目标检测]水面垃圾水面漂浮物检测数据集VOC+YOLO格式3749张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;3749 标注数量(xml文件个数)&#xff1a;3749 标注数量(txt文件个数)&#xff1a;3749 标注…...

[深度学习] 卷积神经网络CNN

卷积神经网络&#xff08;Convolutional Neural Network, CNN&#xff09;是一种专门用于处理数据具有类似网格结构的神经网络&#xff0c;最常用于图像数据处理。 一、CNN的详细过程&#xff1a; 1. 输入层 输入层接收原始数据&#xff0c;例如一张图像&#xff0c;它可以被…...

区别QPushButton和QToolButton

在刚开始学习Qt时,可能很难理解QPushButton和QToolButton之间的区别。 QToolButton通常用于QToolBar中,常常只显示图标,而不显示文本。那么,它们的主要区别是什么?什么时候应该使用QPushButton,什么时候应该使用QToolButton? 了解这一点很重要,这样我们才能选择最合适…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

渗透实战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…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

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

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

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...