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

#P0994. [NOIP2004普及组] 花生采摘

题目描述

鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!――熊字”。

鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格(如图11)。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”

我们假定多多在每个单位时间内,可以做下列四件事情中的一件:

  1. 从路边跳到最靠近路边(即第一行)的某棵花生植株;

  2. 从一棵植株跳到前后左右与之相邻的另一棵植株;

  3. 采摘一棵植株下的花生;

  4. 从最靠近路边(即第一行)的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。

例如在图2所示的花生田里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)(2,5),(3,7),(4,2),(5,4)的植株下长有花生,个数分别为13, 7, 15, 913,7,15,9。沿着图示的路线,多多在2121个单位时间内,最多可以采到3737个花生。

Tips:在采摘过程中不能回到路边哦。

输入格式

第一行包括三个整数,M, NM,N和KK,用空格隔开;表示花生田的大小为M \times N(1 \le M, N \le 20)M×N(1≤M,N≤20),多多采花生的限定时间为K(0 \le K \le 1000)K(0≤K≤1000)个单位时间。接下来的MM行,每行包括NN个非负整数,也用空格隔开;第i + 1i+1行的第jj个整数P_{ij}(0 \le P_{ij} \le 500)Pij​(0≤Pij​≤500)表示花生田里植株(i, j)(i,j)下花生的数目,00表示该植株下没有花生。

输出格式

一个整数,即在限定时间内,多多最多可以采到花生的个数。

输入数据 1

6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

Copy

输出数据 1

37

Copy

输入数据 2

6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

Copy

输出数据 2

28

Copy

来源

NOIP 2004 普及组 第二题

代码:

#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
struct Node{int x,y;int w;
}q[500];//结构体记录有花生的地方以及其价值
int s[25][25];
bool cmp(Node xx,Node yy){return xx.w>yy.w;
}
int main(){int n,m,t,ans=0,k=0;//ans记录答案,k记录有多少个有花生的点cin>>n>>m>>t;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>s[i][j];if(s[i][j]>0){k++;q[k].x=i;q[k].y=j;q[k].w=s[i][j];}}}sort(q+1,q+1+k,cmp);//按照花生价值从大到小将结构体排序for(int i=1;;i++){if(i==1){if(t-(2*q[i].x+1)>=0){ans+=q[i].w;t-=(q[i].x+1);}else{break;}}//i==1是只需要走直线,判断若其进去采摘后可走出则进入采摘,否则结束if(i>1){if((abs(q[i].x-q[i-1].x)+abs(q[i].y-q[i-1].y)+1+q[i].x)<=t){ans+=q[i].w;t-=(abs(q[i].x-q[i-1].x)+abs(q[i].y-q[i-1].y)+1);}else{break;}}//i>1时用曼哈顿距离判断其从上一点到下一点所花费的时间,再加上其采摘和出去的时间,若在规定时间内,则采摘,否则结束}cout<<ans;return 0;
}

 

相关文章:

#P0994. [NOIP2004普及组] 花生采摘

题目描述 鲁宾逊先生有一只宠物猴&#xff0c;名叫多多。这天&#xff0c;他们两个正沿着乡间小路散步&#xff0c;突然发现路边的告示牌上贴着一张小小的纸条&#xff1a;“欢迎免费品尝我种的花生&#xff01;――熊字”。 鲁宾逊先生和多多都很开心&#xff0c;因为花生正…...

Elasticsearch和Kibana的安装及验证

金翅大鹏盖世英&#xff0c;展翅金鹏盖世雄。 穿云燕子锡今鸽&#xff0c;踏雪无痕花云平。 ---------------- 2023.7.31.101 ----------------- 本文密钥&#xff1a;365 Elasticsearch 是一个分布式的 RESTful 风格的搜索和数据分析引擎&#xff0c;常用来进行全文检索、…...

细讲TCP三次握手四次挥手(一)

计算机网络体系结构 在计算机网络的基本概念中&#xff0c;分层次的体系结构是最基本的。计算机网络体系结构的抽象概念较多&#xff0c;在学习时要多思考。这些概念对后面的学习很有帮助。 网络协议是什么&#xff1f; 在计算机网络要做到有条不紊地交换数据&#xff0c;就必…...

【linux-zabbix】zabbix-agent启动报错:Daemon never wrote its PID file. Failing.

背景&#xff1a; 发现有部分的agent失联&#xff0c;排查发现机器正常&#xff0c;agent没起来。 排查日志发现&#xff1a; # journalctl -xe -- Support: http://lists.freedesktop.org/mailman/listinfo/systemd-devel -- -- Unit zabbix-agent.service has begun start…...

【微信小程序】初始化 wxCharts,调用updateData动态更新数据

要初始化 wxCharts&#xff0c;你需要按照以下步骤进行操作&#xff1a; 首先&#xff0c;确保已将 wx-charts.js 文件正确引入到小程序的相应页面或组件中。可以通过以下方式引入&#xff1a; const wxCharts require(../../../../components/wx-charts.js);请根据你的项目…...

【C语言初阶(19)】实用的 VS 调试技巧

文章目录 Ⅰ 调试的介绍Ⅱ 常用调试快捷键Ⅲ 调试的时候查看程序当前信息⒈查看临时变量的值⒉查看内存信息⒊查看调用堆栈⒋查看汇编信息⒌查看寄存器信息 Ⅳ 观察形参指针指向的数组Ⅴ 易于调试的代码该如何编写⒈const 修饰指针变量⒉良好代码示范 Ⅵ 编程中常见的错误 Ⅰ 调…...

虚拟机之间配置免密登录

目录 一、配置主机名映射 二、虚拟机配置SSH免密登录 三、验证 一、配置主机名映射 即修改/etc/hosts文件&#xff0c;将几台服务器和主机名进行映射。 注意每台服务器都要进行同样的配置。这样在各自服务器下&#xff0c;我们就可以通过主机名访问对应的ip地址了。 当然&…...

【contenteditable属性将元素改为可编辑状态】

元素添加contenteditable属性之后点击即可进入编辑状态 像这种只修改一条属性不必再打开弹框进行编辑&#xff0c;使用contenteditable会很方便 添加失焦、回车、获焦事件 如 <p :contenteditable"item.contenteditable || false"keydown.enter"key($event…...

Android 第三方库CalendarView

Android 第三方库CalendarView 根据需求和库的使用方式&#xff0c;自己弄了一个合适自己的日历&#xff0c;仅记录下&#xff0c;方便下次弄其他样式的日历。地址 需求&#xff1a; 只显示当月的数据 默认的月视图有矩形的线 选中的天数也要有选中的矩形框 今天的item需要…...

钉钉群消息推送

1. 添加钉钉群机器人 PC端登录&#xff08;当前版本手机端无法进行推送关键词设置&#xff09;&#xff0c;群设置--> 机器人 --> webhook进行安全设置复制webhook对应的url 2. 群消息推送 钉钉群消息支持纯文本和markdown类型 2.1 调用示例源码 import com.alibaba.…...

css clip-path 属性介绍

circle() – 圆 语法&#xff1a;circle( [<shape-radius>]? [at <position>]? ) shape-radius 圆的半径 position 圆的中心点位置 使用方法&#xff1a; clip-path: circle(); // 以元素的中心点为圆的中心点&#xff0c;最小宽度一半为圆的半径。clip-path: c…...

Python之pyinstaller打包exe填坑总结

一、起因 编写了一个提取图片中文字的python脚本&#xff0c;想传给同事使用&#xff0c;但是同事电脑上没有任何python环境&#xff0c;更没有安装python库&#xff0c;因此想到通过pyinstaller打包成exe程序传给同事使用&#xff0c;于是开始了不断地挖坑填坑之旅 import p…...

Form Generator 表单JSON数据储存以及JSON回显表单

一、form-generator是什么?✨ ⭐️ 🌟 form-generator的作者是这样介绍的:Element UI表单设计及代码生成器,可将生成的代码直接运行在基于Element的vue项目中;也可导出JSON表单,使用配套的解析器将JSON解析成真实的表单。 但目前它提供的组件并不能满足我们在项目中的…...

Python - OpenCV识别条形码、二维码(已封装,拿来即用)

此代码可识别条形码和二维码&#xff0c;已封装好&#xff0c;拿来即用&#xff1a; import cv2 import pyzbar.pyzbar as pyzbar import numpy from PIL import Image, ImageDraw, ImageFontclass CodeScan():def __init__(self):super(CodeScan, self).__init__()def decode…...

Python如何快速实现爬取网页?

首先我们对要编写的爬虫程序进行简单地分析&#xff0c;该程序可分为以下三个部分&#xff1a; 拼接 url 地址发送请求将照片保存至本地 明确逻辑后&#xff0c;我们就可以正式编写爬虫程序了。 导入所需模块 本节内容使用 urllib 库来编写爬虫&#xff0c;下面导入程序所用…...

怎么才能远程控制笔记本电脑?

为什么选择AnyViewer远程控制软件&#xff1f; 为什么AnyViewer是远程控制笔记本电脑软件的首选&#xff1f;以下是选择AnyViewer成为笔记本电脑远程控制软件的主要因素。 跨平台能力 AnyViewer作为一款跨平台远程控制软件&#xff0c;不仅可以用于从一台Windows电…...

【3】C++实现多进程、多线程

系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言一、同步与互斥1、【thread】同步并发的方法(1)创建、终止、等待、分离线程的方法1.创建线程形式1:使用一个循环执行的函数创建一个线程形式2:…...

Linux用户权限信息、chmod以及chown命令

权限修改 权限信息chmod命令chown命令 权限信息 在Linux系统中&#xff0c;每个文件和目录都包含了权限信息&#xff0c;用于控制对其的访问权限。 文件权限&#xff1a;Linux系统中的文件权限由三组权限表示&#xff0c;分别是所有者权限、组权限和其他用户权限。 所有者权…...

利用vscode--sftp,将本地项目/文件上传到远程服务器中详细教程

1、首先在 vscode 中下载 sftp&#xff1a; 2、然后在 vscode 中打开本地将要上传的项目或文件&#xff1a; 3、安装完后&#xff0c;使用快捷键 ctrlshiftP 打开指令窗口&#xff0c;输入 sftp:config &#xff0c;回车&#xff0c;在当前目录中会自动生成 .vscode 文件夹及 s…...

java List和数组相互转换的方法总结

Java中&#xff0c;可以通过以下方法将List转换为数组&#xff1a; List<String> list new ArrayList<>(); String[] array list.toArray(new String[0]);在这个例子中&#xff0c;我们将一个String类型的List转换为String类型的数组。需要注意的是&#xff0c;…...

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

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

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...