MT3017 上色

思路:使用分治,在每个连续区域递归调用heng()和shu()

#include <bits/stdc++.h>
using namespace std;
int n, m;
int h[5005];

int shu(int l, int r)
{
    return r - l + 1;
}
int heng(int l, int r)
{
    int hmin = 0x3f3f3f3f;
    for (int i = l; i <= r; i++)
    { // 取高度的最低值,底下的全部横着刷
        hmin = min(h[i], hmin);
    }
    for (int i = l; i <= r; i++)
    { // 还剩下的没刷的
        h[i] -= hmin;
    }
    int ans = hmin;
    while (l <= r)
    {
        while (l <= r && h[l] == 0)
        { // while结束后,l为高度不为0的左边界
            l++;
        }
        int temp = l; // 从l开始的连续区域
        while (temp <= r && h[temp] != 0)
        { // temp为高度不为0的右边界的下一位
            temp++;
        }
        // 此时计算l-temp区域(对这一区域进行递归调用)
        ans += min(heng(l, temp - 1), shu(l, temp - 1));
        l = temp; // 继续下一区域
    }
    return ans;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    cout << min(heng(1, n), shu(1, n));
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515240.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

关于C#操作SQLite数据库的一些函数封装

主要功能&#xff1a;增删改查、自定义SQL执行、批量执行&#xff08;事务&#xff09;、防SQL注入、异常处理 1.NuGet中安装System.Data.SQLite 2.SQLiteHelper的封装&#xff1a; using System; using System.Collections.Generic; using System.Data.SQLite; using System.…

EDM邮件推广营销工具多少钱?

云衔科技&#xff0c;凭借专业的技术研发实力与丰富的行业经验&#xff0c;倾力打造了一款智能EDM&#xff08;Electronic Direct Mail&#xff09;邮件营销系统解决方案&#xff0c;以精准、高效、定制化的服务&#xff0c;为企业开启全新的营销之旅。至于价格&#xff0c;云衔…

计算机笔记(3)续20个

41.WWW浏览器和Web服务器都遵循http协议 42.NTSC制式30帧/s 44.三种制式电视&#xff1a;NTSC&#xff0c;PAL&#xff0c;SECAM 45.IP&#xff0c;子网掩码白话文简述&#xff1a; A类地址&#xff1a;取值范围0-127&#xff08;四段数字&#xff08;127.0.0.0&#xff09…

Hadoop和zookeeper集群相关执行脚本(未完,持续更新中~)

1、Hadoop集群查看状态 搭建Hadoop数据集群时&#xff0c;按以下路径操作即可生成脚本 [test_1analysis01 bin]$ pwd /home/test_1/hadoop/bin [test_01analysis01 bin]$ vim jpsall #!/bin/bash for host in analysis01 analysis02 analysis03 do echo $host s…

docker安装jenkins 2024版

docker 指令安装安装 docker run -d --restartalways \ --name jenkins -uroot -p 10340:8080 \ -p 10341:50000 \ -v /home/docker/jenkins:/var/jenkins_home \ -v /var/run/docker.sock:/var/run/docker.sock \ -v /usr/bin/docker:/usr/bin/docker jenkins/jenkins:lts访问…

利用Python将TXT文件中的经纬度数据转换为JSON格式

在处理地理空间数据时&#xff0c;经常需要将数据从一种格式转换为另一种格式&#xff0c;以便于后续的分析或可视化。本文将介绍如何使用Python脚本将存储在TXT文件中的经纬度数据转换为JSON格式。 一、背景介绍 经纬度数据是地理信息系统&#xff08;GIS&#xff09;中的基…

关于ansible的模块 ③

转载说明&#xff1a;如果您喜欢这篇文章并打算转载它&#xff0c;请私信作者取得授权。感谢您喜爱本文&#xff0c;请文明转载&#xff0c;谢谢。 接《关于Ansible的模块①》和《关于Ansible的模块②》&#xff0c;继续学习ansible的user模块。 user模块可以增、删、改linux远…

BugKu:Simple SSTI

1.进入此题 2.查看源代码 可以知道要传入一个名为flag的参数&#xff0c;又说我们经常设置一个secret_key 3.flask模版注入 /?flag{{config.SECRET_KEY}} 4.学有所思 4.1 什么是flask&#xff1f; flask是用python编写的一个轻量web开发框架 4.2 SSTI成因&#xff08;SST…

[图解]DDD领域驱动设计伪创新-通用语言05

0 00:00:01,060 --> 00:00:04,370 甚至有的人把这个当成恩典 1 00:00:08,730 --> 00:00:11,500 他认为这个对技术人员有好处 2 00:00:13,010 --> 00:00:14,790 他掌握了主动权 3 00:00:15,730 --> 00:00:16,501 这样的话 4 00:00:16,501 --> 00:00:18,430 你…

CANoe自带的TCP/IP协议栈中TCP的keep alive机制是如何工作的

TCP keep alive机制我们已经讲过太多次,车内很多控制器的TCP keep alive机制相信很多开发和测试的人也配置或者测试过。我们今天想知道CANoe软件自带的TCP/IP协议栈中TCP keep alive机制是如何工作的。 首先大家需要知道TCP keep alive的参数有哪些?其实就三个参数:CP_KEEP…

JVM之常用监控工具

JVM之常用监控工具 jps jinfo 获取配置信息 基本语法 jinfo [options] <pid>常用选项 -sysprops&#xff1a;显示JVM进程的系统属性。-flags&#xff1a;显示用于启动JVM的命令行标志和VM选项。-flag <name>&#xff1a;显示指定JVM标志的当前值。-flag [|-]&…

【JSON2WEB】 12基于Amis-admin的动态导航菜单树

【JSON2WEB】01 WEB管理信息系统架构设计 【JSON2WEB】02 JSON2WEB初步UI设计 【JSON2WEB】03 go的模板包html/template的使用 【JSON2WEB】04 amis低代码前端框架介绍 【JSON2WEB】05 前端开发三件套 HTML CSS JavaScript 速成 【JSON2WEB】06 JSON2WEB前端框架搭建 【J…

Firefox 关键词高亮插件的简单实现

目录 1、配置 manifest.json 文件 2、编写侧边栏结构 3、查找关键词并高亮的方法 3-1&#xff09; 如果直接使用 innerHTML 进行替换 4、清除关键词高亮 5、页面脚本代码 6、参考 1、配置 manifest.json 文件 {"manifest_version": 2,"name": &quo…

配置zookeeper的时候三个节点都启动了但是查询zookeeper的角色的时候显示没启动成功

场景 搭建了一个音乐平台数仓&#xff0c;一共有五个节点&#xff0c;其中三个节点配置zookeeper&#xff0c;我的操作是先把这三个节点的zookeeper全部启动&#xff0c;然后再分别查询各自zookeeper的角色。出现了一下问题&#xff1a; Error contacting service. It is proba…

网络层

网络层主要负责两方面的事情 1.地址管理&#xff1a;制定一系列的规则&#xff0c;通过地址&#xff0c;描述出网络中的设备的位置 2.路由选择&#xff1a;网络环境是非常复杂的。从一个节点到另外一个节点之间&#xff0c;存在很多条不同的路径&#xff0c;通过路由选择来筛…

【nc工具信息传输】

nc&#xff0c;全名叫 netcat&#xff0c;它可以用来完成很多的网络功能&#xff0c;譬如端口扫描、建立TCP/UDP连接&#xff0c;数据传输、网络调试等等&#xff0c;因此&#xff0c;它也常被称为网络工具的 瑞士军刀 。 nc [-46DdhklnrStUuvzC] [-i interval] [-p source_po…

3.恒定乘积自动做市商算法及代码

中心化交易所的安全风险 在中心化交易所中注册账户时&#xff0c;是由交易所生成一个地址&#xff0c;用户可以向地址充币&#xff0c;充到地址之后交易所就会根据用户充币的数量显示在管理界面中。但是充币的地址是掌管在交易所之中的&#xff0c;资产的控制权还是在交易所。…

【Java多线程(4)】案例:设计模式

目录 一、什么是设计模式&#xff1f; 二、单例模式 1. 饿汉模式 2. 懒汉模式 懒汉模式-第一次改进 懒汉模式-第二次改进 懒汉模式-第三次改进 一、什么是设计模式&#xff1f; 设计模式是针对软件设计中常见问题的通用解决方案。它们提供了一种被广泛接受的方法来解决…

【2024系统架构设计】案例分析- 5 Web应用

目录 一 基础知识 二 真题 一 基础知识 1 Web应用技术分类 大型网站系统架构的演化:高性能、高可用、可维护、应变、安全。 从架构来看:MVC,MVP,MVVM,REST,Webservice,微服务。

从头开发一个RISC-V的操作系统(一)计算机系统漫游

文章目录 前提计算机的硬件组成程序的存储与执行操作系统 目标&#xff1a;通过这一个系列课程的学习&#xff0c;开发出一个简易的在RISC-V指令集架构上运行的操作系统。 前提 这个系列的大部分文章和知识来自于&#xff1a;[完结] 循序渐进&#xff0c;学习开发一个RISC-V上…