17098 广告牌最佳安放问题

这个问题可以通过动态规划来解决。我们可以定义一个数组d,其中d[i]表示到第i个广告牌地点时可以选择放置广告牌的最大效益值。然后我们可以通过遍历所有可能的j(1 <= j <= i && x[i] - x[j] > 5),然后更新d[i]为max(d[i-1], d[j] + r[i])。

以下是解题步骤:

1. 初始化数组:首先,我们需要初始化一个数组d,并将d[1]设置为r[1]。

2. 动态规划:然后,我们可以使用动态规划来更新d数组。对于每一个i(i > 1),我们可以遍历所有可能的j(1 <= j <= i && x[i] - x[j] > 5),然后更新d[i]为max(d[i-1], d[j] + r[i])。

3. 输出结果:最后,d[n]就是我们要求的最大效益值。

以下是使用C++实现的代码:

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100001;
int x[MAXN], r[MAXN], d[MAXN];

int main() {
    int M, n;
    cin >> M >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> r[i];
    }
    d[1] = r[1];
    for (int i = 2; i <= n; ++i) {
        d[i] = d[i - 1];
        for (int j = 1; j < i; ++j) {
            if (x[i] - x[j] > 5) {
                d[i] = max(d[i], d[j] + r[i]);
            }
        }
    }
    cout << d[n] << endl;
    return 0;
}

这段代码首先读取公路长度和广告牌的总数,然后读取每个广告牌的位置和收益。然后,它使用动态规划的方法来计算最大的收益。最后,它输出最大的收益。

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

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

相关文章

【云原生】ptcpdump捕获任何进程、容器或 Pod 的网络流量的抓包神器——筑梦之路

ptcpdump 是一个使用 eBPF 技术开发的、类 tcpdump 的网络抓包工具。它除了兼容 tcpdump 的常用命令行参数以及包过滤语法外&#xff0c; 还额外提供了如下核心特性&#xff1a; 在输出中记录和显示发送网络流量的进程、容器、Pod 信息。 支持对指定进程、容器以及 Pod 进行抓…

LED显示屏中什么情况下用网线?什么情况下用光纤?

在这个色彩斑斓的数字时代&#xff0c;LED显示屏如同城市的眼睛&#xff0c;闪烁着各种信息与艺术的光芒。而要让这些“眼睛”明亮有神&#xff0c;背后离不开两条重要的“信息高速公路”——网线和光纤。它们就像是LED显示屏的血管&#xff0c;负责输送数据这一“血液”。那么…

实验三:图像的平滑滤波

目录 一、实验目的 二、实验原理 1. 空域平滑滤波 2. 椒盐噪声的处理 三、实验内容 四、源程序和结果 (1) 主程序&#xff08;matlab&#xff09; (2) 函数GrayscaleFilter (3) 函数MeanKernel (4) 函数MedFilter 五、结果分析 1. 空域平滑滤波 2. 椒盐噪声的处理…

Python PDF文件的加密和水印处理使用详解

概要 在日常工作中,处理PDF文件是非常常见的需求。为了保护PDF文件的内容,我们可能需要对其进行加密。同时,为了防止文件被未经授权的复制和使用,添加水印也是一种有效的方法。本文将详细介绍如何使用Python对PDF文件进行加密和添加水印的操作,包含详细的示例代码,帮助全…

嵌入式系统中的GPIO控制与应用

GPIO是嵌入式系统中最常见且功能最强大的接口之一。它允许硬件工程师通过编程来配置和控制芯片上的数字引脚&#xff0c;实现输入和输出的功能。在本文中&#xff0c;我们将从理论和实践两个方面探讨GPIO的工作原理&#xff0c;并通过一个简单的示例项目来演示如何利用GPIO控制…

IP风险画像 金融行业的安全盾牌

在当今数字化时代&#xff0c;金融行业面临着前所未有的安全挑战。随着在线交易和数字银行业务的迅猛发展&#xff0c;欺诈和网络攻击的威胁也在不断增加。金融机构需要高效、可靠的安全解决方案来保护客户的资产和个人信息&#xff0c;防止各种形式的欺诈行为。 IP风险画像是…

CS110L(Rust)

1.Rust 语法总结 数值类型 有符号整数: i8, i16, i32, i64无符号整数: u8, u16, u32, u64 变量声明 声明变量: let i 0; // 类型推断let n: i32 1; // 显式类型声明 可变变量: let mut n 0; n n 1; 字符串 注意&#xff0c;let s: str "Hello world";…

WebSocket、服务器推送技术

WebSocket 是一种在单个 TCP 连接上进行 全双工 通信的协议&#xff0c;它可以让客户端和服务器之间进行实时的双向通信&#xff0c;且不存在同源策略限制 WebSocket 使用一个长连接&#xff0c;在客户端和服务器之间保持持久的连接&#xff0c;从而可以实时地发送和接收数据…

区块链与云计算的融合:新时代数据安全的挑战与机遇

随着信息技术的迅猛发展&#xff0c;云计算和区块链技术作为两大前沿技术在各自领域内展示出了巨大的潜力。而它们的结合&#xff0c;即区块链与云计算的融合&#xff0c;正在成为数据安全领域的新趋势。本文将探讨这一融合对数据安全带来的挑战和机遇&#xff0c;以及其在企业…

django实现用户的注册、登录、注销功能

创建django项目的步骤&#xff1a;Django项目的创建步骤-CSDN博客 一、前置工作 配置数据库&#xff0c;设置数据库引擎为mysql 1、在settings文件中找到DATABASES, 配置以下内容 DATABASES {"default": {ENGINE: django.db.backends.mysql, # 数据库引擎NAME: dja…

【数据结构与算法】希尔排序:基于插入排序的高效排序算法

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​ 目录 一、引言 二、基本原理 三、实现步骤 四、C语言实现 五、性能分析 1. 时间复杂度…

Hadoop3:HDFS-查看logs文件,排查NameNode故障原因。

问题一、NameNode进程退出 我们发现&#xff0c;NameNode进程不存在。 情况1、单独启动NameNode hdfs --daemon start namenode能够正常拉起&#xff0c;那就没问题 情况2、无法独立启动NameNode 先尝试启动NameNode hdfs --daemon start namenode发现&#xff0c;没能成…

el-date-picker手动输入日期,通过设置开始时间和阶段自动填写结束时间

需求&#xff1a;根据开始时间&#xff0c;通过填写阶段时长&#xff0c;自动填写结束时间&#xff0c;同时开始时间和节数时间可以手动输入 代码如下&#xff1a; <el-form ref"ruleForm2" :rules"rules2" :model"formData" inline label-po…

Redis深度解析:从基础到高级特性,剖析关键技术

一、关于Redis Redis介绍 REmote DIctionary Server(Redis) 是一个由 Salvatore Sanfilippo 写的 key-value 存储系统&#xff0c;是跨平台的非关系型数据库。 Redis 是一个开源的使用 ANSIC 语言编写、遵守 BSD&#xff08;开源协议&#xff09; 协议、支持网络、可基于内存…

指令判断数据更改,文本变色

默认数据是这样&#xff0c;如果更改了其中一个&#xff0c;文本框变成红色 <el-form-item label"Activity name"><el-inputv-model"form.name"v-highlight"datas[name]"input"changeValue(name)"/></el-form-item>…

excel系列(二) - 利用 easypoi 快速实现 excel 文件导入导出

一、介绍 在上篇文章中&#xff0c;我们介绍了 apache poi 工具实现 excel 文件的导入导出。 本篇我们继续深入介绍另一款优秀的 excel 工具库&#xff1a;easypoi。 二、easypoi 以前的以前&#xff0c;有个大佬程序员&#xff0c;跳到一家公司之后就和业务人员聊上了&…

智慧水利:迈向水资源管理的新时代,结合物联网、云计算等先进技术,阐述智慧水利解决方案在提升水灾害防控能力、优化水资源配置中的关键作用

本文关键词&#xff1a;智慧水利、智慧水利工程、智慧水利发展前景、智慧水利技术、智慧水利信息化系统、智慧水利解决方案、数字水利和智慧水利、数字水利工程、数字水利建设、数字水利概念、人水和协、智慧水库、智慧水库管理平台、智慧水库建设方案、智慧水库解决方案、智慧…

LLM-阿里 DashVector + langchain self-querying retriever 优化 RAG 实践【Query 优化】

文章目录 前言self querying 简介代码实现总结 前言 现在比较流行的 RAG 检索就是通过大模型 embedding 算法将数据嵌入向量数据库中&#xff0c;然后在将用户的查询向量化&#xff0c;从向量数据库中召回相似性数据&#xff0c;构造成 context template, 放到 LLM 中进行查询…

HCIE是什么等级的证书?

HCIE&#xff08;华为认证互联网专家&#xff0c;Huawei Certified Internetwork Expert&#xff09;是华为认证体系中的最高等级证书。它要求考生具备在复杂网络环境中规划、设计、部署、运维和优化网络的能力。HCIE认证是华为认证体系中最具挑战性和含金量的认证之一&#xf…

MWA(Modern Web App)初学那些事-2-Basic HTML CSS

初学MWA(Modern Web App&#xff09;那些事-2-Basic HTML & CSS 目录 初学MWA(Modern Web App&#xff09;那些事-2-Basic HTML & CSS前言一、本节学习目标二、HTML基础内容2.1关键元素2.4 Scripts 三、CSS 基础内容3.1 级联样式表-用于设置网页样式和布局3.2 CSS规则语…