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

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

原文地址：https://blog.csdn.net/huang1xiao1sheng/article/details/140409171

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！