Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP2605 [ZJOI2010]基站选址

Posted on In
Symbols count in article: 3k Reading time ≈ 3 mins.

线段树优化转移

基站选址

思路

考虑 dp ，设 $d[i, j, k]$ 表示“前 $i$ 个村子选了 $j$ 个，最后一个为 $k$ ”的最小代价，转移方程很好写，设 $v(x, y)$ 表示“当 $x, y$ 上面都有基站时 $x \sim y$ 的点的代价”：
$$
d[i, j, k] \gets
\begin{cases}
d[i - 1, j, k] + v(k, i) \\
d[i - 1, j - 1, i] + c[i]
\end{cases}
$$
然后，发现寄了，因为状态数就是 $O(n^2m)$ 的（这里 $m$ 就是题目的 $k$ ），必须优化状态，发现我们之所以要记录最后一个是 $k$ ，是因为我们还要考虑 $k$ 以后的点的代价，不妨新加一个点 $n + 1$ ，它的距离为 $\infty$ （无法被前面覆盖），不被覆盖的代价为 $\infty$ （必须被覆盖），在它这里建基站的代价为 $0$ （不影响答案），然后让 $m += 1$ ，这样就保证最后一个基站一定建在 $n + 1$ 上，那么我们就只考虑前面的代价即可

设 $d[i, j]$ 表示“前 $i$ 个村子选了 $j$ 个，且最后一个就在 $i$ 时前 $i$ 个村子的代价”，那么转移为：
$$
d[i, j] \gets d[k, j - 1] + v(k, i) + c[i]
$$
状态数是 $O(nm)$ ，直接转移是 $O(n)$ ，又爆炸了，考虑优化，发现 $c[i]$ 是定值，对于每个 $i$ 如果可以快速查出 $\min(d[k, j - 1] + v(k, i))$ 就好了，那么最直接的思路就是用线段树维护 $d[k, j - 1] + v(k, i)$ （对于每个 $j$ 重新建一次树）

$d[k, j - 1]$ 是不随 $i$ 变化的，考虑 $v(k, i)$ 的变化：

cg

如图，对于点 $k$ ，设包含它的范围为 $lp \sim rp$ ，那么在如图 $i \to i + 1$ 跨 $rp$ 时，自然会使得 $0 \sim lp - 1$ 的位置代价加 $w[k]$ ，对于每个点二分出 $lp, rp$ ，线段树维护即可

时间 $O(mn \log n + n \log n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define pb push_back
const int N = 2e4 + 100, K = 100 + 100, INF = 0x3f3f3f3f;
int n, num;
int d[K][N], ans = INF;
int c[N], dis[N], s[N], w[N], lp[N];
std::vector<int> cg[N];
namespace LT
{
    #define lc (u << 1)
    #define rc ((u << 1) | 1)
    #define mid ((l + r) >> 1)
    int v[N << 2], tg[N << 2];
    void up(int u){ v[u] = std::min(v[lc], v[rc]); }
    void adt(int u, int d){ tg[u] += d, v[u] += d; }
    void dw(int u)
    {
        if (tg[u])
        {
            adt(lc, tg[u]), adt(rc, tg[u]);
            tg[u] = 0;
        }
    }
    void bd(int x[], int u = 1, int l = 0, int r = n)
    {
        v[u] = INF, tg[u] = 0;
        if (l == r) return void(v[u] = x[l]);
        bd(x, lc, l, mid), bd(x, rc, mid + 1, r);
        up(u);
    }
    void mdf(int ql, int qr, int d, int u = 1, int l = 0, int r = n)
    {
        if (l >= ql && r <= qr) return adt(u, d);
        dw(u);
        if (ql <= mid) mdf(ql, qr, d, lc, l, mid);
        if (qr > mid) mdf(ql, qr, d, rc, mid + 1, r);
        up(u);
    }
    int qry(int ql, int qr, int u = 1, int l = 0, int r = n)
    {
        if (l >= ql && r <= qr) return v[u];
        dw(u);
        int res = INF;
        if (ql <= mid) res = qry(ql, qr, lc, l, mid);
        if (qr > mid) res = std::min(qry(ql, qr, rc, mid + 1, r), res);
        return res;
    }
    #undef lc
    #undef rc
    #undef mid
}
int findr(int x, int st)
{
    int l = st, r = n, mid, res = n;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (dis[mid] <= x) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}
int findl(int x, int st)
{
    int l = 1, r = st, mid, res = st;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (dis[mid] >= x) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}
int main()
{
    scanf("%d %d", &n, &num);
    for (int i = 2; i <= n; ++i) scanf("%d", &dis[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &s[i]);
        cg[findr(dis[i] + s[i], i)].pb(i);
        lp[i] = findl(dis[i] - s[i], i);
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    ++n, ++num;
    dis[n] = w[n] = INF, c[n] = 0;
    memset(d, 0x3f, sizeof d);
    d[0][0] = 0;
    for (int j = 1; j <= num; ++j)
    {
        LT::bd(d[j - 1]);
        for (int i = 1; i <= n; ++i)
        {
            d[j][i] = LT::qry(0, i - 1) + c[i];
            for (int t : cg[i]) LT::mdf(0, lp[t] - 1, w[t]);
        }
    }
    for (int i = 0; i <= num; ++i) ans = std::min(ans, d[i][n]);
    printf("%d\n", ans);
    return 0;
}