洛谷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;
}