M 国要在 A 城市与 B 城市之间建设 5G 基站,已知 A 城市与 B 城市的距离为 nn 千米,工程师们已经考察在从 A 城市往 B 城市方向上 1,2,...,n 千米处建设 5G 基站的成本,分别是 w1w1,w2w2,...,wnwn。 为了保证通信质量,5G 基站的选址还需要满足 mm 条需求,其中第 ii 条需求可以用 lili 和 riri 表示 (1≤li≤ri≤n1≤li≤ri≤n),代表从 A 城市往 B 城市方向上 lili 千米到 riri 千米的位置之间(含两端)至少需要建设 1 座 5G 基站。 作为总工程师,您需要决定 5G 基站的数量与位置,并计算满足所有需求的最小总成本。 输入格式 第一行输入两个整数 nn 和 mm 分别表示距离和需求数量。 接下来一行输入 nn 个整数 w1w1,w2w2,...,wnwn 分别表示从 A 城市往 B 城市方向上 1,2,...,nn 千米处建设 5G 基站的成本。 接下来 mm 行,第 i 行输入两个整数 lili 和 riri(1≤li≤ri≤n1≤li≤ri≤n) 表示从 A 城市往 B 城市方向上 lili 千米到 riri 千米的位置之间(含两端)至少需要建设 1 座 5G 基站。 输出格式 输出一行一个整数,表示满足所有需求的最小总成本。 用c++
时间: 2024-03-23 09:42:35 浏览: 10
以下是该问题的C++代码实现:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int w[N], sum[N];
int q[N], hh, tt;
int f[N];
int get(int j, int k)
{
return f[j] + sum[j] * sum[j] - f[k] - sum[k] * sum[k];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + w[i];
hh = tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh < tt && get(q[hh], q[hh + 1]) <= 2 * sum[i] * (sum[q[hh]] - sum[q[hh + 1]])) hh ++ ;
int j = q[hh];
f[i] = f[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;
while (hh < tt && get(q[tt - 1], q[tt]) * (sum[q[tt]] - sum[q[tt - 1]]) >= get(q[tt], i) * (sum[q[tt - 1]] - sum[i])) tt -- ;
q[ ++ tt] = i;
}
printf("%d\n", f[n]);
return 0;
}
```
时间复杂度:$O(n)$