17098 广告牌最佳安放问题

server/2024/12/22 2:56:18/

这个问题可以通过动态规划来解决。我们可以定义一个数组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;
}

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


http://www.ppmy.cn/server/60023.html

相关文章

Django 实现子模版继承父模板

背景 Django的占位符&#xff0c;如果不继承父模板的内容&#xff0c;会被子模版所覆盖&#xff0c;有些业务场景子模版也需要使用到父模板中的内容 可以使用Django自带的标签{% block super %}来实现此效果 base.html 最基础html&#xff0c;相当于第一层html&#xff0c;bl…

3D云渲染工具对决:Maya与Blender的性能和功能深度比较

3D建模和动画制作已成为数字领域不可或缺的一环&#xff0c;无论是在影视特效的震撼场面&#xff0c;还是在游戏角色的生动表现&#xff0c;3D技术都扮演着至关重要的角色。而在这一领域&#xff0c;Maya和Blender这两款软件&#xff0c;以其强大的功能和广泛的应用&#xff0c…

mysql 导出导入 数据库

导出 MySQL 数据库可以通过多种方法实现&#xff0c;最常见的方法是使用 mysqldump 工具。以下是一些常用的导出 MySQL 数据库的方法&#xff1a; 使用 mysqldump 工具 mysqldump 是一个命令行工具&#xff0c;用于导出 MySQL 数据库的结构和数据。以下是基本的导出命令&…

2、ASPX、.NAT(环境/框架)安全

ASPX、.NAT&#xff08;环境/框架&#xff09;安全 源自小迪安全b站公开课 1、搭建组合&#xff1a; WindowsIISaspxsqlserver .NAT基于windows C开发的框架/环境 对抗Java xx.dll <> xx.jar 关键源码封装在dll文件内。 2、.NAT配置调试-信息泄露 功能点&#xf…

【Redis】Redis十大类型

文章目录 前言一、string字符串类型二、List列表类型三、 Hash表四、 Set集合五、 ZSet有序集合六、 GEO地理空间七、 HyperLogLog基数统计八、Bitmap位图九、bitfield位域十、 Stream流10.1 队列指令10.2 消费组指令10.3 ACK机制 前言 redis是k-v键值对进行存储&#xff0c;k…

MySQL CONCAT函数的简单使用

CONCAT函数用于将mysql中查询多列的值拼成一列显示&#xff0c; 使用示例&#xff1a; SELECT CONCAT(attr_name,"&#xff1a;",attr_value) FROM pms_sku_sale_attr_value WHERE sku_id1; 上面SQL语句使用CONCAT函数将attr_name、attr_value两列的值拼成一列&am…

设计模式使用场景实现示例及优缺点(结构型模式——组合模式)

结构型模式 组合模式&#xff08;Composite Pattern&#xff09; 组合模式使得用户对单个对象和组合对象的使用具有一致性。 有时候又叫做部分-整体模式&#xff0c;它使我们树型结构的问题中&#xff0c;模糊了简单元素和复杂元素的概念&#xff0c;客户程序可以像处理简单元…

C++ 入门10:继承和派生类

往期回顾&#xff1a; C 入门07&#xff1a;静态成员和常量成员-CSDN博客 C 入门08&#xff1a;运算符重载-CSDN博客 C 入门09&#xff1a;友元函数和友元类-CSDN博客 一、前言 在前面文章的学习中&#xff0c;我们了解了类和对象的基础知识、构造函数、拷贝构造函数、静态成员…