[CF1253E] Antenna Coverage - dp

[CF1253E] Antenna Coverage - dp

Description

街道上有 \(n \le 80\) 个天线。第 \(i\) 个天线的位置为 \(x_i\)，以及一个范围值 \(s_i\)；第 \(i\) 个天线的覆盖范围是 \([x_i-s_i,x_i+s_i]\)。每次操作，你可以花费 \(1\) 代价，使得第 \(i\) 个天线的 \(s_i\) 增加一。每个天线都可以进行多次操作。现在请问你最少需要花费多少代价，使 \([1,m] (m \le 10^5)\) 编号内的每一个位置都被至少一个天线覆盖。

Solution

设 \(f[i]\) 表示 \([1,i]\) 被全部覆盖的最小花费，初态 \(f[i]=i\)

如果 i 已经被某个初始区间完全覆盖了，那么可以从 \(f[i-1]\) 转移过来

另一种转移是，有一个区间要扩张，枚举每个区间，这里我们只取左边的区间向右扩张

如果区间的右端点在 i 左边，那么可以考虑这个区间扩张后恰好覆盖到 i 的左端点的情况，也就是从 \(f_{l_j-i+r_j)+i-r_j\) 转移过来

为什么不同时取右边的区间向左扩张？假设方案中右边有个区间在后面扩张了，那么转移的时候取的转移来源会更偏左……，因此，对于同一个点而言，转移到它的所有状态中，转移点靠右的状态一定不会更劣

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;

signed main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<int> x(n + 2), s(n + 2), l(n + 2), r(n + 2), f(m + 2);
    for (int i = 1; i <= m; i++)
        f[i] = i;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> s[i];
        l[i] = x[i] - s[i];
        r[i] = x[i] + s[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int flag = 0;
        for (int j = 1; j <= n; j++)
            if (l[j] <= i && r[j] >= i)
                flag = 1;
        if (flag)
        {
            f[i] = f[i - 1];
        }

        for (int j = 1; j <= n; j++)
        {
            if (r[j] < i)
            {
                f[i] = min(f[i], f[max(0ll, l[j] - i + r[j] - 1)] + i - r[j]);
            }
        }
    }
    cout << f[m] << endl;
}