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

洛谷 P1048 [NOIP2005 普及组] 采药

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗?

输入格式

第一行有 22 个整数 TT(1 \le T \le 10001≤T≤1000)和 MM(1 \le M \le 1001≤M≤100),用一个空格隔开,TT 代表总共能够用来采药的时间,MM 代表山洞里的草药的数目。

接下来的 MM 行每行包括两个在 11 到 100100 之间(包括 11 和 100100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入 #1复制

70 3
71 100
69 1
1 2

输出 #1复制

3

说明/提示

【数据范围】

  • 对于 30\%30% 的数据,M \le 10M≤10;
  • 对于全部的数据,M \le 100M≤100。

【题目来源】

NOIP 2005 普及组第三题

代码如下:
 

#include<bits/stdc++.h>
using namespace std;
int f[105][1005];
int w[105];		//w数组表示采摘每个草药需要的时间;  
int v[105];		//v数组表示草药的价值; 
int main(){int n,m;scanf("%d %d",&n,&m);		//n表示总共能够用来采药的时间,m代表山洞里的草药的数目。for(int i=1;i<=m;i++){scanf("%d %d",&w[i],&v[i]);} for(int i=1;i<=m;i++){for(int j=0;j<=n;j++){f[i][j]=f[i-1][j];if(j>=w[i]){f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);}}}printf("%d",f[m][n]);return 0;
}

相关文章:

洛谷 P1048 [NOIP2005 普及组] 采药

辰辰是个天资聪颖的孩子&#xff0c;他的梦想是成为世界上最伟大的医师。为此&#xff0c;他想拜附近最有威望的医师为师。医师为了判断他的资质&#xff0c;给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说&#xff1a;“孩子&#xff0c;这个山洞里有一些不同…...

VMware vSphere虚拟化基础管理平台

VMware简介 VMware介绍 官网&#xff1a;https://www.vmware.com/cn.html VMware公司成立于1998年&#xff0c;2003年存储厂商EMC以6.35亿美元收购了VMware&#xff1b;2015年10月&#xff0c;戴尔宣布以670亿美元收购EMC。VMware公司在2018年全年收入79.2亿美元。 VMware主…...

leetcode刷题-代码训练营-第7章-回溯算法1

回溯法模板 void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择&#xff1a;本层集合中元素&#xff08;树中节点孩子的数量就是集合的大小&#xff09;) {处理节点;backtracking(路径&#xff0c;选择列表); // 递归回溯&#xff0c;撤销处理结果} }理解 从…...

三种常见webshell工具的流量特征分析

又来跟师傅们分享小技巧了&#xff0c;这次简单介绍一下三种常见的webshell流量分析&#xff0c;希望能对参加HW蓝队的师傅们有所帮助。 什么是webshell webshell就是以asp、php、jsp或者cgi等网页文件形式存在的一种代码执行环境&#xff0c;主要用于网站管理、服务器管理、…...

pkg打包nodejs程序用动态require路由出现问题

动态路由问题 pkg打包的时候会自动生成一个虚拟路径/snapshot/…会导致你的路径出现一些问题 而项目中依据route文件夹下的文件动态use相应的router&#xff0c;这就需要动态require&#xff0c;但是这个require的路径会被虚拟路径代替导致取不到&#xff0c;所以可以使用写死…...

设计模式(018)行为型之策略模式

策略模式是一种行为设计模式&#xff0c;它定义了一系列算法&#xff0c;将每个算法封装成一个对象&#xff0c;并使它们可以互换。策略模式使得算法的变化可以独立于使用算法的客户端。在策略模式中&#xff0c;有三个核心角色&#xff1a;策略接口&#xff08;Strategy&#…...

c++关键字: =delete和=default

delete 概述 delete关键字是c11新增的关键字&#xff0c;主要用于的场景是&#xff1a;当我们不希望类中的函数被类对象在外部调用的时候&#xff0c;我们就可以使用这个关键字。 其实&#xff0c;之前我们实现这种功能是将这些函数放在private修饰符下&#xff0c;但是这种方…...

JSON

文章目录 JSONJSON 的定义格式快速入门JSON 对象和字符串对象转换JSON 在 java 中使用JSON与java对象的转换JSON与List集合的转换JSON与Map的转换 JSON JSON 指的是 JavaScript 对象表示法&#xff08;JavaScript Object Notation&#xff09; JSON 是轻量级的文本数据交换格式…...

Python | 超前滞后分析

Nino SST Indices (Nino 12, 3, 3.4, 4; ONI and TNI) 有几个指标用于监测热带太平洋&#xff0c;所有这些指标都是基于海表温度(SST)异常在一个给定的区域的平均值。通常&#xff0c;异常是相对于30年的周期来计算的。厄尔尼诺3.4指数(Nio 3.4 index)和海洋厄尔尼诺指数(Ocea…...

Linux CPU利用率

Linux CPU利用率 在线上服务器观察线上服务运行状态的时候&#xff0c;绝大多数人都是喜欢先用 top 命令看看当前系统的整体 cpu 利用率。例如&#xff0c;随手拿来的一台机器&#xff0c;top 命令显示的利用率信息如下 这个输出结果说简单也简单&#xff0c;说复杂也不是那么…...

vue3实现导出pdf、png功能

准备做的系统中出现了 想导出当前页面的png或者pdf设计数据较多后端做可能比较麻烦 就自己研究了一下 1、安装html2canvas 、jspdf包 npm install --save html2canvas // 可以将dom元素转为一张图片 npm install --save jspdf // 导出为PDF格式 2、vue组件中引用&#x…...

what is tty?

waht is tty? 黑话&#xff1a;TTY 为什么使用Linux的时候CtrlC就会终止一个命令运行,ta是如何设置的? stty -a 桌面切换 CTRL ALT F1 – 锁屏 CTRL ALT F2 – 桌面环境 CTRL ALT F3 – TTY3 CTRL ALT F4 – TTY4 CTRL ALT F5 – TTY5 CTRL ALT F6 – TTY6...

在vite中限制node版本

1.修改package.json文件 {"name": "wine-store-frontend","version": "0.0.0","private": true,"type": "module","scripts": {"dev": "vite --open","build"…...

07 Php学习:运算符

PHP 算术运算符 在 PHP 中&#xff0c;算术运算符用于执行基本的数学运算&#xff0c;包括加法、减法、乘法、除法、取余数&#xff0c;负数运算、取反和并置运算。以下是这些运算符的详细解释和示例&#xff1a; 加法运算符 &#xff1a;用于将两个数值相加。 $a 5; $b 3;…...

做了多年前端,有没有想在python,go,nodejs,.net,java,c++中学一门后端,推荐

作为一名经验丰富的前端开发者&#xff0c;选择学习后端技术是一个重要的职业发展决策。Python、Go、Node.js、.NET、Java和C都是强大的后端开发语言&#xff0c;每门语言都有其特定的优势和应用场景。以下是对这些技术的分析&#xff0c;以帮助你做出选择&#xff1a; 目录 …...

JR-SMD201-P便携式网络解码器

详细介绍&#xff1a; JR-SMD201-P便携式网络解码器采用1/2U设计&#xff0c;支持AVS/H.265/H.264/MPEG2解码&#xff0c;支持IP输入&#xff0c;支持1080P/1080I/720P/576I/480I多种分辨率&#xff0c;支持DRA/AC3/EAC3/AAC/MPEG等音频。 产品特点 支持输入方式IP 接口丰富&a…...

线程池阻塞队列的选择

一、背景 想起前两年被问到阻塞队列怎么选&#xff0c;有界是必然的&#xff0c; ArrayBlockingQueue、LinkedBlockingQueue怎么选呢。 二、打开源码看看 ArrayBlockingQueue arrayBlockingQueue new ArrayBlockingQueue(3);LinkedBlockingQueue linkedBlockingQueue new Lin…...

linux内核驱动-在内核代码里添加设备结点

linux中&#xff0c;一切皆文件 我们在用户层用一些系统函数&#xff08;如&#xff1a;fopen等等&#xff09;时&#xff0c;会进入内核&#xff0c;内核会在字符注册了的设备号链表中查找。如果找到就运行我们写的设备文件的&#xff08;驱动&#xff09;函数 我们在前面已经…...

【算法优选】 动态规划之简单多状态dp问题——贰

文章目录 &#x1f38b;前言&#x1f334;[买卖股票的最佳时机含冷冻期](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/)&#x1f6a9;题目描述&#x1f6a9;算法思路&#xff1a;&#x1f388;状态表示&#xff1a;&#x1f388;…...

【算法刷题 | 二叉树 06】4.10( 路径总和、路径总和 || )

文章目录 13.路径总和13.1问题13.2解法一&#xff1a;递归13.2.1递归思路&#xff08;1&#xff09;确定递归函数参数以及返回值&#xff08;2&#xff09;确定终止条件&#xff08;3&#xff09;确定递归逻辑 13.2.2代码实现 14.路径总和 ||14.1问题14.2解法一&#xff1a;递归…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...