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

The Wedding Juicer POJ - 2227

采取从外层边界,一步一步向内部拓展的策略,具体来说,一开始将最外面一层的点加入队列,并标记这些点的坐标已经被访问

取出队列中高度最低的点,将其弹出,查看其上下左右的点,如果新点没有被访问过,分两种情况:
1.如果新点的高度大于等于当前点:将新点加入队列,标记新点已经访问过了,该点无法储水

2.如果新点的高度小于当前点:则新点储水(当前点的高度 - 新点的高度),首先,这么多水一定可以存,因为当前点的高度是边界高度中最小的,其次,这是能存的最多的水,因为再多就超过了当前点高度,所以这个点能储存的水,在这种策略下,是所求的最大解,将储水结果累加进ans,并且将这个新点的高度改成当前点的高度后,标记新点坐标已访问,将新点加入队列中

不断重复以上操作,直到队列为空

复杂度略

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;#define ll long longconst ll maxn=305;
ll w,h,ans;
ll a[maxn][maxn],vis[maxn][maxn];
ll dx[]={-1,1,0,0},dy[]={0,0,-1,1};struct node{ll x,y,h;node(ll x=0,ll y=0,ll h=0):x(x),y(y),h(h) {}bool operator < (const node &rhs) const {return h>rhs.h;}
};int main()
{ios::sync_with_stdio(0);cin.tie(0);cin>>w>>h;for(ll i=1;i<=h;i++){for(ll j=1;j<=w;j++){cin>>a[i][j];}}priority_queue<node> q;//将最外一层加入队列for(int i=1;i<=w;i++){if(vis[1][i]==0) {vis[1][i]=1;q.push(node(1,i,a[1][i]));}if(vis[h][i]==0) {vis[h][i]=1;q.push(node(h,i,a[h][i]));}}for(int i=1;i<=h;i++){if(vis[i][1]==0){vis[i][1]=1;q.push(node(i,1,a[i][1]));}if(vis[i][w]==0){vis[i][w]=1;q.push(node(i,w,a[i][w]));}}/*while(q.size()){node t=q.top();q.pop();printf("(%lld,%lld)\n",t.x,t.y);}*/while(q.size()){node t=q.top();q.pop();ll x=t.x,y=t.y,h1=t.h;for(ll i=0;i<4;i++){ll nx=x+dx[i],ny=y+dy[i];if(nx<1 || nx>h || ny<1 || ny>w) continue;if(vis[nx][ny]) continue;if(a[nx][ny]>=h1) {q.push(node(nx,ny,a[nx][ny]));vis[nx][ny]=1;}else {ans+=h1-a[nx][ny];q.push(node(nx,ny,h1));vis[nx][ny]=1;}}}cout<<ans<<"\n";return 0;
}

相关文章:

The Wedding Juicer POJ - 2227

采取从外层边界&#xff0c;一步一步向内部拓展的策略&#xff0c;具体来说&#xff0c;一开始将最外面一层的点加入队列&#xff0c;并标记这些点的坐标已经被访问 取出队列中高度最低的点&#xff0c;将其弹出&#xff0c;查看其上下左右的点&#xff0c;如果新点没有被访问…...

# 深入理解RNN(一):循环神经网络的核心计算机制

深入理解RNN&#xff1a;循环神经网络的核心计算机制 RNN示意图 引言 在自然语言处理、时间序列预测、语音识别等涉及序列数据的领域&#xff0c;循环神经网络(RNN)一直扮演着核心角色。尽管近年来Transformer等架构逐渐成为主流&#xff0c;RNN的基本原理和思想依然对于理…...

分布式锁—6.Redisson的同步器组件

大纲 1.Redisson的分布式锁简单总结 2.Redisson的Semaphore简介 3.Redisson的Semaphore源码剖析 4.Redisson的CountDownLatch简介 5.Redisson的CountDownLatch源码剖析 1.Redisson的分布式锁简单总结 (1)可重入锁RedissonLock (2)公平锁RedissonFairLock (3)联锁MultiL…...

同步 Fork 仓库的命令

同步 Fork 仓库的命令 要将您 fork 的仓库的 main 分支与原始仓库&#xff08;fork 源&#xff09;同步&#xff0c;您可以使用以下命令&#xff1a; 首先&#xff0c;确保您已经添加了原始仓库作为远程仓库&#xff08;如果尚未添加&#xff09;&#xff1a; git remote add…...

基于PySide6的CATIA零件自动化着色工具开发实践

引言 在汽车及航空制造领域&#xff0c;CATIA作为核心的CAD设计软件&#xff0c;其二次开发能力对提升设计效率具有重要意义。本文介绍一种基于Python的CATIA零件着色工具开发方案&#xff0c;通过PySide6实现GUI交互&#xff0c;结合COM接口操作实现零件着色自动化。该方案成…...

OpenManus 的提示词

OpenManus 的提示词 引言英文提示词的详细内容工具集的详细说明中文翻译的详细内容GitHub 仓库信息背景分析总结 引言 OpenManus 是一个全能 AI 助手&#xff0c;旨在通过多种工具高效地完成用户提出的各种任务&#xff0c;包括编程、信息检索、文件处理和网页浏览等。其系统提…...

Ubuntu-docker安装mysql

只记录执行步骤。 1 手动下载myql镜像&#xff08;拉去华为云镜像&#xff09; docker pull swr.cn-east-3.myhuaweicloud.com/library/mysql:latest配置并启动mysql 在opt下创建文件夹 命令&#xff1a;cd /opt/ 命令&#xff1a;mkdir mysql_docker 命令&#xff1a;cd m…...

Electron桌面应用开发:自定义菜单

完成初始应用的创建Electron桌面应用开发&#xff1a;创建应用&#xff0c;随后我们就可以自定义软件的菜单了。菜单可以帮助用户快速找到和执行命令&#xff0c;而不需要记住复杂的快捷键&#xff0c;通过将相关功能组织在一起&#xff0c;用户可以更容易地发现和使用应用程序…...

理解 JavaScript 中的浅拷贝与深拷贝

在 JavaScript 开发中&#xff0c;我们经常需要复制对象或数组。然而&#xff0c;复制的方式不同&#xff0c;可能会导致不同的结果。本文将详细介绍 浅拷贝 和 深拷贝 的概念、区别以及实现方式&#xff0c;帮助你更好地理解和使用它们。 1. 什么是浅拷贝&#xff1f; 定义 …...

【Java开发指南 | 第三十五篇】Maven + Tomcat Web应用程序搭建

读者可订阅专栏&#xff1a;Java开发指南 |【CSDN秋说】 文章目录 前言Maven Tomcat Web应用程序搭建1、使用Maven构建新项目2、单击项目&#xff0c;连续按两次shift键&#xff0c;输入"添加"&#xff0c;选择"添加框架支持"3、选择Java Web程序4、点击&…...

从0到1入门Linux

一、常用命令 ls 列出目录内容 cd切换目录mkdir创建新目录rm删除文件或目录cp复制文件或目录mv移动或重命名文件和目录cat查看文件内容grep在文件中查找指定字符串ps查看当前进程状态top查看内存kill终止进程df -h查看磁盘空间存储情况iotop -o直接查看比较高的磁盘读写程序up…...

golang 从零单排 (一) 安装环境

1.下载安装 打开网址The Go Programming Language 直接点击下载go1.24.1.windows-amd64.msi 下载完成 直接双击下一步 下一步 安装完成 环境变量自动设置不必配置 2.验证 win r 输入cmd 打开命令行 输入go version...

如何下载和使用Git:初学者指南

&#x1f31f; 如何下载和使用Git&#xff1a;初学者指南 在当今的软件开发中&#xff0c;Git已经成为不可或缺的版本控制系统。无论你是独立开发者还是团队成员&#xff0c;掌握Git的基本操作都能帮助你更高效地管理代码。今天&#xff0c;我将详细介绍如何下载和使用Git&…...

SQL_语法

1 数据库 1.1 新增 create database [if not exists] 数据库名; 1.2 删除 drop database [if exists] 数据库名; 1.3 查询 (1) 查看所有数据库 show databases; (2) 查看当前数据库下的所有表 show tables; 2 数据表 2.1 新增 (1) 创建表 create table [if not exists…...

基于Python实现的智能旅游推荐系统(Django)

基于Python实现的智能旅游推荐系统(Django) 开发语言:Python 数据库&#xff1a;MySQL所用到的知识&#xff1a;Django框架工具&#xff1a;pycharm、Navicat 系统功能实现 总体设计 系统实现 系统首页模块 统首页页面主要包括首页&#xff0c;旅游资讯&#xff0c;景点信息…...

安孚科技携手政府产业基金、高能时代发力固态电池,开辟南孚电池发展新赛道

安孚科技出手&#xff0c;发力固态电池。 3月7日晚间&#xff0c;安孚科技&#xff08;603031.SH&#xff09;发布公告称&#xff0c;公司控股子公司南孚电池拟与南平市绿色产业投资基金有限公司&#xff08;下称“南平绿色产业基金”&#xff09;、高能时代&#xff08;广东横…...

p5.js:模拟 n个彩色小球在一个3D大球体内部弹跳

向 豆包 提问&#xff1a;编写一个 p5.js 脚本&#xff0c;模拟 42 个彩色小球在一个3D大球体内部弹跳。每个小球都应留下一条逐渐消失的轨迹。大球体应缓慢旋转&#xff0c;并显示透明的轮廓线。请确保实现适当的碰撞检测&#xff0c;使小球保持在球体内部。 cd p5-demo copy…...

Kali WebDAV 客户端工具——Cadaver 与 Davtest

1. 工具简介 在 WebDAV 服务器管理和安全测试过程中&#xff0c;Cadaver 和 Davtest 是两款常用的命令行工具。 Cadaver 是一个 Unix/Linux 命令行 WebDAV 客户端&#xff0c;主要用于远程文件管理&#xff0c;支持文件上传、下载、移动、复制、删除等操作。Davtest 则是一款…...

MySQL复习笔记

MySQL复习笔记 1.MySQL 1.1什么是数据库 数据库(DB, DataBase) 概念&#xff1a;数据仓库&#xff0c;软件&#xff0c;安装在操作系统&#xff08;window、linux、mac…&#xff09;之上 作用&#xff1a;存储数据&#xff0c;管理数据 1.2 数据库分类 关系型数据库&#…...

六十天前端强化训练之第十四天之深入理解JavaScript异步编程

欢迎来到编程星辰海的博客讲解 目录 一、异步编程的本质与必要性 1.1 单线程的JavaScript运行时 1.2 阻塞与非阻塞的微观区别 1.3 异步操作的性能代价 二、事件循环机制深度解析 2.1 浏览器环境的事件循环架构 核心组件详解&#xff1a; 2.2 执行顺序实战分析 2.3 Nod…...

Simulink Assignment模块实战:如何像写C代码一样更新数组元素?

Simulink Assignment模块实战&#xff1a;从C语言思维到模型化设计的无缝衔接 对于习惯用C语言编写控制算法的工程师来说&#xff0c;第一次接触Simulink的模块化设计往往会感到不适应——尤其是当需要更新数组中的特定元素时。在C语言中&#xff0c;我们只需简单地写下array[2…...

别再死记硬背了!用数字电路里的‘上升沿’和‘下降沿’来理解epoll的ET模式(附Linux C++代码演示)

从数字电路到高性能IO&#xff1a;用硬件思维理解epoll的边沿触发模式 当你在示波器上观察一个时钟信号时&#xff0c;工程师们最关心的往往不是电平本身的高低&#xff0c;而是电平跳变的瞬间——那个被称为"边沿"的微妙时刻。这种硬件设计中的经典概念&#xff0c;…...

实测Taotoken API调用延迟与稳定性在SpringBoot服务中的表现

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 实测Taotoken API调用延迟与稳定性在SpringBoot服务中的表现 在将大模型能力集成到后端微服务时&#xff0c;开发者不仅关注功能的…...

手把手带你用C语言模拟RISC-V的`li`指令扩展过程(附完整代码)

手把手带你用C语言模拟RISC-V的li指令扩展过程&#xff08;附完整代码&#xff09; 在计算机体系结构的学习中&#xff0c;理解指令集的工作原理是掌握底层编程的关键。RISC-V作为一种开源指令集架构&#xff0c;近年来在学术界和工业界都获得了广泛关注。本文将带领读者通过C语…...

IO-Link技术解析:工业自动化通信与LTC2874/LT3669芯片应用

1. IO-Link技术概述&#xff1a;工业自动化的神经末梢在工业4.0的浪潮中&#xff0c;设备间的实时通信如同工厂的神经系统。IO-Link作为这个系统中的"神经末梢"&#xff0c;实现了控制层与现场设备间的最后一米连接。这项技术最早由PROFIBUS用户组织在2009年推出&…...

Python pip升级报错怎么办_强制更新与重新安装pip方法

...

RT-Thread Smart下基于74LV595的KSZ8081网卡复位与驱动移植实战

1. 硬件连接与复位逻辑解析 第一次拿到i.MX6ULL开发板时&#xff0c;我发现KSZ8081网卡的复位引脚竟然接在了74LV595芯片上&#xff0c;这和常见的直接连接GPIO的设计完全不同。这种设计虽然节省了GPIO资源&#xff0c;但给驱动开发带来了新挑战。 74LV595是典型的串行输入并行…...

测试环境搭建指南:从零开始构建完善的测试体系

测试环境搭建指南&#xff1a;从零开始构建完善的测试体系 前言 各位前端小伙伴&#xff0c;不知道你们有没有这样的经历&#xff1a;在自己电脑上测试好好的&#xff0c;一到CI环境就各种失败。 我曾经因为测试环境和生产环境不一致&#xff0c;导致线上出现了一个严重bug。后…...

Syzygy-of-Thoughts:用代数几何思想提升大语言模型推理能力

1. 项目概述&#xff1a;当大语言模型遇上代数几何如果你最近在折腾大语言模型&#xff08;LLM&#xff09;的推理能力提升&#xff0c;大概率听说过“思维链”&#xff08;Chain of Thought, CoT&#xff09;和“自洽性”&#xff08;Self-Consistency, CoT-SC&#xff09;这些…...

工资到账前,先把个税摸个底

工资到账前&#xff0c;先把个税摸个底 什么是个税 「个税」通常指个人所得税。对大多数上班族来说&#xff0c;最常见的是工资薪金所得&#xff1a;公司发你税前工资&#xff0c;按规定预扣预缴一部分税款交给税务&#xff1b;你到手的「实发」已经扣过税了。除此之外&#…...