17098 广告牌最佳安放问题

这个问题可以通过动态规划来办理。我们可以定义一个数组d，此中d表示到第i个广告牌地点时可以选择放置广告牌的最大效益值。然后我们可以通过遍历所有大概的j（1 <= j <= i && x - x[j] > 5），然后更新d为max(d[i-1], d[j] + r)。
以下是解题步调：
1. 初始化数组：起首，我们必要初始化一个数组d，并将d[1]设置为r[1]。
2. 动态规划：然后，我们可以使用动态规划来更新d数组。对于每一个i（i > 1），我们可以遍历所有大概的j（1 <= j <= i && x - x[j] > 5），然后更新d为max(d[i-1], d[j] + r)。
3. 输出结果：最后，d[n]就是我们要求的最大效益值。
以下是使用C++实现的代码：

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
5. const int MAXN = 100001;
6. int x[MAXN], r[MAXN], d[MAXN];
8. int main() {
9.     int M, n;
10.     cin >> M >> n;
11.     for (int i = 1; i <= n; ++i) {
12.         cin >> x[i];
13.     }
14.     for (int i = 1; i <= n; ++i) {
15.         cin >> r[i];
16.     }
17.     d[1] = r[1];
18.     for (int i = 2; i <= n; ++i) {
19.         d[i] = d[i - 1];
20.         for (int j = 1; j < i; ++j) {
21.             if (x[i] - x[j] > 5) {
22.                 d[i] = max(d[i], d[j] + r[i]);
23.             }
24.         }
25.     }
26.     cout << d[n] << endl;
27.     return 0;
28. }

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。