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;
}

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


http://www.niftyadmin.cn/n/5558379.html

相关文章

百度大数据开发面试题集锦及参考答案(持续更新)

目录 Java GC算法有哪些? 项目中遇到过的有关GC的情况,相关的设置参数 存储引擎、B+树和B树的区别、B+树的结构实现 布隆过滤器 内存的管理方式、虚拟内存和物理内存的区别 TCP、UDP、TCP三次四次握手、如何保证可靠传输 数据仓库主题域及其建设过程 数仓的指标体系构…

在 Debian 12 上安装 budgie-extras-common 包

在 Debian 12 上安装 budgie-extras-common 包&#xff1a; 安装前的准备 更新 apt 数据库&#xff1a; 使用 apt-get:sudo apt-get update或者使用 apt:sudo apt update如果使用 aptitude&#xff08;通常不在 Debian 默认安装中&#xff09;&#xff0c;首先需要安装它&…

如何防止Eclipse格式化程序在行注释开头插入空格

格式化前&#xff1a; //foo bar 格式化后&#xff1a; // foo bar 这种看着不是很舒服。如果不让格式化时自动在注释符后面插入空格呢&#xff1f; 要在Eclipse中进行代码格式化时防止在行注释&#xff08;‌//&#xff09;‌后面自动增加空格&#xff0c;‌可以通过调整…

自建Web网站部署——案例分析

作者主页: 知孤云出岫 目录 作者主页:如何自建一个Web网站一、引言二、需求分析三、技术选型四、开发步骤1. 项目初始化初始化前端初始化后端 2. 前端开发目录结构示例代码App.jsHome.js 3. 后端开发目录结构示例代码app.jsproductRoutes.jsProduct.js 4. 前后端连接安装axio…

RK3568 V1.4.0 SDK,USB OTG端子不能被电脑识别出adb设备,解决

修改后的/usr/bin/usbdevice: #!/bin/sh # # Usage: # usbdevice [start|update|stop] # # Hookable stages: # usb_<pre|post>_<init|prepare|start|stop|restart>_hook # <usb function>_<pre|post>_<prepare|start|stop>_hook # # Example …

Hadoop中HDFS、Hive 和 HBase三者之间的关系

HDFS&#xff08;Hadoop Distributed File System&#xff09;、Hive 和 HBase 是 Hadoop 生态系统中三个重要的组件&#xff0c;它们各自解决了大数据存储和处理的不同层面的问题。我们用大白话来解释这三个组件之间的关系&#xff1a; HDFS - 数据的仓库&#xff1a; HDFS 是…

【入门篇】2.3 STM32启动模式(一)

一,Boot引脚分步 二,启动电路 三,启动模式 STM32F4 根据 BOOT 引脚的电平选择启动模式,这两个 BOOT 引脚根据外部施加的电平来决定芯片的启动地址。 下表中 BOOT0 和 BOOT1 是 STM32 芯片上面的两个引脚,用于控制 STM32

常见的五种聚类算法总结

常见的聚类算法总结 1. K-Means 聚类 描述 K-Means 是一种迭代优化的聚类算法&#xff0c;它通过最小化样本点到质心的距离平方和来进行聚类。 思想 随机选择 K 个初始质心。分配每个数据点到最近的质心&#xff0c;形成 K 个簇。重新计算每个簇的质心。重复上述步骤&…