当前位置: 首页 > 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…...

3分钟掌握暗黑破坏神2存档编辑器:免费在线工具让你的游戏体验全面升级

3分钟掌握暗黑破坏神2存档编辑器&#xff1a;免费在线工具让你的游戏体验全面升级 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor 还在为刷不到心仪的装备而烦恼吗&#xff1f;想要快速体验不同职业的乐趣却不想重新练级&#x…...

ComfyUI IPAdapter Plus完整配置指南:图像条件控制的终极解决方案

ComfyUI IPAdapter Plus完整配置指南&#xff1a;图像条件控制的终极解决方案 【免费下载链接】ComfyUI_IPAdapter_plus 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI_IPAdapter_plus ComfyUI IPAdapter Plus是Stable Diffusion图像生成中实现精准图像条件控制…...

AK7739 TDM调试避坑指南:从tinymix命令到SA6125平台时钟极性BUG排查

AK7739 TDM音频接口深度调试&#xff1a;从寄存器配置到时钟极性异常实战解析 当我们在嵌入式音频系统中集成AK7739编解码器时&#xff0c;TDM&#xff08;时分复用&#xff09;接口的调试往往是工程师面临的最大挑战之一。不同于标准的I2S协议&#xff0c;TDM接口的高度可配置…...

如何用XiaoMusic让小爱音箱变身你的私人音乐管家:5个超实用场景解析

如何用XiaoMusic让小爱音箱变身你的私人音乐管家&#xff1a;5个超实用场景解析 【免费下载链接】xiaomusic 使用小爱音箱播放音乐&#xff0c;音乐使用 yt-dlp 下载。 项目地址: https://gitcode.com/GitHub_Trending/xia/xiaomusic 还在为小爱音箱只能播放特定平台的音…...

深入Logos FPGA的PCB布局:如何针对FBG256、FBG484和LPG封装优化你的设计

深入Logos FPGA的PCB布局&#xff1a;如何针对FBG256、FBG484和LPG封装优化你的设计 在硬件设计领域&#xff0c;FPGA的PCB布局一直是工程师面临的核心挑战之一。特别是当项目需要在性能、成本和尺寸之间寻找平衡点时&#xff0c;封装选择往往成为决定成败的关键因素。Logos系列…...

【Matlab】MATLAB教程:Simulink与MATLAB交互(MATLAB函数模块案例+混合编程仿真)

MATLAB教程:Simulink与MATLAB交互(MATLAB函数模块案例+混合编程仿真) 本教程适配MATLAB R2020a及以上版本,聚焦Simulink与MATLAB交互核心技能,以MATLAB函数模块为核心案例,详解混合编程仿真的全流程,无需深厚编程基础,纯实操导向、案例可直接复刻,适配高校课程设计、…...

基于Next.js urborepo的企业级电商全栈架构实战解析

1. 项目概述与核心价值最近在梳理企业级电商项目的技术选型与架构方案&#xff0c;发现了一个非常值得深入研究的开源项目——Blazity/enterprise-commerce。这不仅仅是一个简单的电商模板&#xff0c;而是一个基于Next.js 14、TypeScript和Turborepo构建的现代化、全栈式企业级…...

AgenticTime:为AI智能体设计的时间推理引擎与.atime文件格式详解

1. 项目概述&#xff1a;为AI智能体赋予时间感知能力如果你用过Claude、GPT或者任何基于大语言模型的AI助手&#xff0c;肯定遇到过这样的场景&#xff1a;你告诉它“周五前要完成API评审”&#xff0c;它当时答应得好好的&#xff0c;但当你隔天再问“我这周有什么要紧事”时&…...

Deep3D:开启2D视频实时转3D的视觉革命

Deep3D&#xff1a;开启2D视频实时转3D的视觉革命 【免费下载链接】Deep3D Real-Time end-to-end 2D-to-3D Video Conversion, based on deep learning. 项目地址: https://gitcode.com/gh_mirrors/dee/Deep3D 你是一个文章写手&#xff0c;你负责为开源项目写专业易懂的…...

喷墨设备怎么选?2026年UV喷码技术深度评测与选购指南

面对市场上琳琅满目的工业喷墨设备&#xff0c;尤其是UV喷墨设备厂家&#xff0c;采购者如何做出明智选择&#xff1f;本文将从技术前沿、核心参数与行业应用三大维度&#xff0c;为您提供一份详尽的评测与选购指南&#xff0c;并深度剖析以中防uv喷码机为代表的专业制造商如何…...