Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P2605 [ZJOI2010]基站选址

发表于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟
标签：            

P2605 [ZJOI2010]基站选址

$f _ {i, j}$ 表示在前 $i$ 个村庄中，建设 $j$ 个基站且第 $i$ 个基站是被选择前 $i$ 个村庄的最小代价，考虑外层枚举 $j$ ，那么做 $m$ 次线性DP：
$$
f _ i = \min _ {j < i} \{f _ j + cost _ i + w _ {j + 1, i}\}
$$
发现一段区间的代价不能很快速地计算。

考虑 $lp _ i, rp _ i$ 表示点 $i$ 最左、右侧可以使得 $i$ 被覆盖的点。考虑用线段树维护可供转移的 $j$ ，即线段树第 $i$ 个位置上的数为 $f _ i + w _ {i + 1, cur}$ ，$f _ i$ 上一个基站选择后得到的答案是不变的；$w _ {i + 1, cur}$ 的值随着当前 $cur$ 的变化而变化。如果当前考虑的基站 $cur$ 已经不能覆盖到一个村庄 $j$ ，如果前面的基站也不能覆盖到这个村庄，那么随着 $cur$ 增大，一定依然需要村庄 $j$ 的补偿。

那么，对于每一个基站，考虑所有被当前基站覆盖并且不能被下一个基站覆盖的村庄 $j$ ，$lp _ j$ 左侧的基站不能覆盖 $j$ ，将村庄 $j$ 的补偿增加到这些转移中。

查看代码 
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
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e4 + 10, inf = 2e9;
int n, m, dis[N], cst[N], rg[N], wt[N], lp[N], rp[N], f[N];
vector <int> g[N];
struct Node
{
    int l, r, mn, tag;
} tr[N << 2];
void pushup (int x)
{
    tr[x].mn = min(tr[x << 1].mn, tr[x << 1 | 1].mn);
}
void add (int x, int k)
{
    tr[x].mn += k, tr[x].tag += k;
}
void pushdown (int x)
{
    add(x << 1, tr[x].tag), add(x << 1 | 1, tr[x].tag);
    tr[x].tag = 0;
}
void build (int l = 1, int r = n, int x = 1)
{
    tr[x].l = l, tr[x].r = r, tr[x].tag = 0;
    if (l == r)
        return void(tr[x].mn = f[l]);
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
void modify (int l, int r, int k, int x = 1)
{
    if (tr[x].l > r || l > tr[x].r || l > r)
        return;
    if (tr[x].l >= l && tr[x].r <= r)
        return add(x, k);
    pushdown(x);
    modify(l, r, k, x << 1), modify(l, r, k, x << 1 | 1);
    pushup(x);
}
int query (int l, int r, int x = 1)
{
    if (tr[x].l > r || l > tr[x].r || l > r)
        return inf;
    if (tr[x].l >= l && tr[x].r <= r)
        return tr[x].mn;
    pushdown(x);
    return min(query(l, r, x << 1), query(l, r, x << 1 | 1));
}
int main ()
{
    read(n), read(m);
    for (int i = 2; i <= n; i++)
        read(dis[i]);
    for (int i = 1; i <= n; i++)
        read(cst[i]);
    for (int i = 1; i <= n; i++)
        read(rg[i]);
    for (int i = 1; i <= n; i++)
        read(wt[i]);
    n++, m++;
    dis[n] = wt[n] = inf;
    for (int i = 1; i <= n; i++)
    {
        lp[i] = lower_bound(dis + 1, dis + n + 1, dis[i] - rg[i]) - dis;
        rp[i] = upper_bound(dis + 1, dis + n + 1, dis[i] + rg[i]) - dis - 1;
        g[rp[i]].push_back(i);
    }
    for (int i = 1, cur = 0; i <= n; i++)
    {
        f[i] = cur + cst[i];
        for (int j : g[i])
            cur += wt[j];
    }
    int res = f[n];
    for (int k = 2; k <= m; k++)
    {
        build();
        for (int i = 1; i <= n; i++)
        {
            f[i] = query(1, i - 1) + cst[i];
            for (int j : g[i])
                modify(1, lp[j] - 1, wt[j]);
        }
        res = min(res, f[n]);
    }
    write(res);
    return 0;
}
相关文章