洛谷P2605 [ZJOI2010] 基站选址题解

题目链接：P2605 [ZJOI2010] 基站选址

题意：

有 \(N\) 个村庄坐落在一条直线上，第 \(i(i>1)\) 个村庄距离第 \(1\) 个村庄的距离为 \(D_i\)。需要在这些村庄中建立不超过 \(K\) 个通讯基站，在第 \(i\) 个村庄建立基站的费用为 \(C_i\)。如果在距离第 \(i\) 个村庄不超过 \(S_i\) 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 \(i\) 个村庄没有被覆盖，则需要向他们补偿，费用为 \(W_i\)。现在的问题是，选择基站的位置，使得总费用最小。

输入格式：

输入文件的第一行包含两个整数 \(N,K\)，含义如上所述。

第二行包含 \(N-1\) 个整数，分别表示 \(D_2,D_3,\cdots,D_N\) ，这 \(N-1\) 个数是递增的。

第三行包含 \(N\) 个整数，表示 \(C_1,C_2,\cdots,C_N\)。

第四行包含 \(N\) 个整数，表示 \(S_1,S_2,\cdots,S_N\)。

第五行包含 \(N\) 个整数，表示 \(W_1,W_2,\cdots,W_N\)。

输出格式：

输出文件中仅包含一个整数，表示最小的总费用。

数据范围：

\(1\le K\leq 100,~1 \le K \le N\leq 2\times 10^4,~0 \le D_i,S_i \leq 10^9,~0 \le C_i,W_i \leq 10^4\) 。

线段树优化dp经典题。

首先设 \(f(i,j)\) 表示仅考虑前 \(i\) 个村庄，放了 \(j\) 个基站的最小花费，钦定 \(i\) 必须放基站。

方便起见，预处理出 \(g(l,r)\) 表示 \(l,r\) 放了基站后 \((l,r)\) 没有被覆盖的花费。

考虑令 \(n+1\) 为特殊的必选基站，并令 \(n \gets n + 1,~m \gets m + 1\) ，那么 \[ f(i,j) = \min\{f(k,j-1) + g(k,i) \} + c_i \quad (j - 1 \le k < i) \] 考虑优化。首先 \(j\) 可以在外层枚举，然后滚动数组，变成 \[ f_i = \min\{f_k + g(k,i)\} + c_i \] 不过预处理 \(g(k,i)\) 还是太慢。由于 \(i\) 是递增的，所以考虑用线段树维护一个数组 \(g\) 。

接着考虑记录 \(L_i,R_i\) 表示 \(i\) 最左和最右能覆盖到的点，这个可以二分得到。

然后记录每个 \(i\) 有哪些 \(k\) 满足 \(R_k=i\) ，在处理 \(i+1\) 之前，

将这些 \(k\) 将要给 \(g\) 带来的花费在线段树上维护，这是一个区间加法，查询的话是区间最小值。

呃，反正就这个意思，可能说的不太清楚，详见代码吧，~~现在好困有点懒得讲~~

时间复杂度 \(\mathcal{O}(nk \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e4 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, m, pos = 1, d[N], c[N], s[N], w[N], L[N], R[N], f[N], head[N];
struct Edge { int v, next; } e[N];
struct node { int v, t; } tr[N * 4];
void addEdge(int u, int v) { e[++pos] = {v, head[u]}; head[u] = pos; }
void push_up(int at) { down(tr[at].v = tr[ls(at)].v, tr[rs(at)].v); }
void build(int l = 1, int r = n, int at = 1)
{
    if(l == r) { tr[at] = {f[l], 0}; return; }
    int mid = (l + r) >> 1; tr[at].t = 0;
    build(l, mid, ls(at)); build(mid + 1, r, rs(at)); push_up(at);
}
void push_down(int at)
{
    if(!tr[at].t) return;
    tr[ls(at)].v += tr[at].t; tr[rs(at)].v += tr[at].t;
    tr[ls(at)].t += tr[at].t; tr[rs(at)].t += tr[at].t; tr[at].t = 0;
}
void update(int nl, int nr, int k, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr) { tr[at].v += k; tr[at].t += k; return; }
    int mid = (l + r) >> 1; push_down(at);
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
    push_up(at);
}
int query(int nl, int nr, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr) return tr[at].v;
    int mid = (l + r) >> 1, res = INF; push_down(at);
    if(nl <= mid) down(res, query(nl, nr, l, mid, ls(at)));
    if(nr > mid) down(res, query(nl, nr, mid + 1, r, rs(at)));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 2, n) cin >> d[i]; rep(i, 1, n) cin >> c[i];
    rep(i, 1, n) cin >> s[i]; rep(i, 1, n) cin >> w[i];
    ++n; ++m; d[n] = w[n] = INF;
    rep(i, 1, n)
    {
        L[i] = lower_bound(d + 1, d + 1 + n, d[i] - s[i]) - d;
        R[i] = upper_bound(d + 1, d + 1 + n, d[i] + s[i]) - d - 1;
        addEdge(R[i], i);
    }
    int sum = 0, res = 0;
    rep(i, 1, n)
    {
        f[i] = sum + c[i];
        for(int k = head[i]; k; k = e[k].next)
            sum += w[e[k].v];
    }
    res = f[n];
    rep(j, 2, m)
    {
        build();
        rep(i, 1, n)
        {
            f[i] = (i > j - 1 ? query(j - 1, i - 1) : 0) + c[i];
            for(int k = head[i], v; k; k = e[k].next)
                if(L[v = e[k].v] > 1) update(1, L[v] - 1, w[v]);
        }
        down(res, f[n]);
    }
    cout << res << '\n';
    return 0;
}