本文主要是介绍3. Antenna Coverage，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Antenna Coverage
数轴上有 n n n 个天线，每个天线都有一定的辐射范围，可以支付 k k k 的费用让某个天线的辐射半径增加 k k k，可以任意执行修改操作，问覆盖区间 [ 1 , m ] [1,m] [1,m] 的最少费用。
各种贪心似乎都是不行的。观察数据范围， O ( n m ) O(nm) O(nm) 的复杂度可以通过。尝试 dp，令 d p [ i ] dp[i] dp[i] 表示覆盖到 i i i 位置的最少费用，如果 i i i 已经被覆盖，直接从 d p [ i − 1 ] dp[i-1] dp[i−1] 转移，否则枚举之前的所有天线 j j j 作为覆盖当前位置的天线，假设这种情况下延长的半径为 k k k，则从 d p [ j − r j − k − 1 ] dp[j-r_j-k-1] dp[j−rj−k−1] 处转移。
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
int dp[maxn];
pii p[maxn];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1, x, s; i <= n; ++i) {cin >> x >> s;p[i] = {max(0, x - s), min(m, x + s)};}dp[0] = 0;for (int i = 1; i <= m; ++i) {dp[i] = i;for (int j = 1; j <= n; ++j) {if (p[j].first <= i && p[j].second >= i)dp[i] = min(dp[i], dp[i - 1]);else if (p[j].second < i) {int d = i - p[j].second;dp[i] = min(dp[i], dp[max(0, p[j].first - d - 1)] + d);}}}cout << dp[m] << '\n';
}
这篇关于3. Antenna Coverage的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
