洛谷 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 普及组] 采药
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同…...
VMware vSphere虚拟化基础管理平台
VMware简介 VMware介绍 官网:https://www.vmware.com/cn.html VMware公司成立于1998年,2003年存储厂商EMC以6.35亿美元收购了VMware;2015年10月,戴尔宣布以670亿美元收购EMC。VMware公司在2018年全年收入79.2亿美元。 VMware主…...
leetcode刷题-代码训练营-第7章-回溯算法1
回溯法模板 void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果} }理解 从…...
三种常见webshell工具的流量特征分析
又来跟师傅们分享小技巧了,这次简单介绍一下三种常见的webshell流量分析,希望能对参加HW蓝队的师傅们有所帮助。 什么是webshell webshell就是以asp、php、jsp或者cgi等网页文件形式存在的一种代码执行环境,主要用于网站管理、服务器管理、…...
pkg打包nodejs程序用动态require路由出现问题
动态路由问题 pkg打包的时候会自动生成一个虚拟路径/snapshot/…会导致你的路径出现一些问题 而项目中依据route文件夹下的文件动态use相应的router,这就需要动态require,但是这个require的路径会被虚拟路径代替导致取不到,所以可以使用写死…...
设计模式(018)行为型之策略模式
策略模式是一种行为设计模式,它定义了一系列算法,将每个算法封装成一个对象,并使它们可以互换。策略模式使得算法的变化可以独立于使用算法的客户端。在策略模式中,有三个核心角色:策略接口(Strategy&#…...
c++关键字: =delete和=default
delete 概述 delete关键字是c11新增的关键字,主要用于的场景是:当我们不希望类中的函数被类对象在外部调用的时候,我们就可以使用这个关键字。 其实,之前我们实现这种功能是将这些函数放在private修饰符下,但是这种方…...
JSON
文章目录 JSONJSON 的定义格式快速入门JSON 对象和字符串对象转换JSON 在 java 中使用JSON与java对象的转换JSON与List集合的转换JSON与Map的转换 JSON JSON 指的是 JavaScript 对象表示法(JavaScript Object Notation) JSON 是轻量级的文本数据交换格式…...
Python | 超前滞后分析
Nino SST Indices (Nino 12, 3, 3.4, 4; ONI and TNI) 有几个指标用于监测热带太平洋,所有这些指标都是基于海表温度(SST)异常在一个给定的区域的平均值。通常,异常是相对于30年的周期来计算的。厄尔尼诺3.4指数(Nio 3.4 index)和海洋厄尔尼诺指数(Ocea…...
Linux CPU利用率
Linux CPU利用率 在线上服务器观察线上服务运行状态的时候,绝大多数人都是喜欢先用 top 命令看看当前系统的整体 cpu 利用率。例如,随手拿来的一台机器,top 命令显示的利用率信息如下 这个输出结果说简单也简单,说复杂也不是那么…...
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? 黑话: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 中,算术运算符用于执行基本的数学运算,包括加法、减法、乘法、除法、取余数,负数运算、取反和并置运算。以下是这些运算符的详细解释和示例: 加法运算符 :用于将两个数值相加。 $a 5; $b 3;…...
做了多年前端,有没有想在python,go,nodejs,.net,java,c++中学一门后端,推荐
作为一名经验丰富的前端开发者,选择学习后端技术是一个重要的职业发展决策。Python、Go、Node.js、.NET、Java和C都是强大的后端开发语言,每门语言都有其特定的优势和应用场景。以下是对这些技术的分析,以帮助你做出选择: 目录 …...
JR-SMD201-P便携式网络解码器
详细介绍: JR-SMD201-P便携式网络解码器采用1/2U设计,支持AVS/H.265/H.264/MPEG2解码,支持IP输入,支持1080P/1080I/720P/576I/480I多种分辨率,支持DRA/AC3/EAC3/AAC/MPEG等音频。 产品特点 支持输入方式IP 接口丰富&a…...
线程池阻塞队列的选择
一、背景 想起前两年被问到阻塞队列怎么选,有界是必然的, ArrayBlockingQueue、LinkedBlockingQueue怎么选呢。 二、打开源码看看 ArrayBlockingQueue arrayBlockingQueue new ArrayBlockingQueue(3);LinkedBlockingQueue linkedBlockingQueue new Lin…...
linux内核驱动-在内核代码里添加设备结点
linux中,一切皆文件 我们在用户层用一些系统函数(如:fopen等等)时,会进入内核,内核会在字符注册了的设备号链表中查找。如果找到就运行我们写的设备文件的(驱动)函数 我们在前面已经…...
【算法优选】 动态规划之简单多状态dp问题——贰
文章目录 🎋前言🌴[买卖股票的最佳时机含冷冻期](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/)🚩题目描述🚩算法思路:🎈状态表示:🎈…...
【算法刷题 | 二叉树 06】4.10( 路径总和、路径总和 || )
文章目录 13.路径总和13.1问题13.2解法一:递归13.2.1递归思路(1)确定递归函数参数以及返回值(2)确定终止条件(3)确定递归逻辑 13.2.2代码实现 14.路径总和 ||14.1问题14.2解法一:递归…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
