BZOJ1835 基站选址

题面

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

题解

这题优化比较奇妙
设 $f[i][j]$ 为考虑前 $i$ 个村都被计算过,建立了 $j$ 个基站,并且第 $i$ 村上一定建了基站的最小花费

那么有转移
$$ f[i][j]=min{f[k][j-1]+cost(k,i)|k<i} $$
其中 $cost(k,i)$ 表示在 $k,i$ 建立基站而不在 $(k,i)$ 中建的补偿花费
直接转移肯定 TLE ,所以考虑优化
首先肯定可以枚举第二维为外层循环然后通过滚动压掉第二维
接下来考虑如何维护 $[1,i)$ 中 $f[k]+cost(k,i)$ 的最小值
考虑对于某一个 $k$ ,在什么时候 $(k,i)$ 中会多出一些点需要补偿花费
也就是 $k,i$ 都无法覆盖 $j(j\in (k,i))$ 时
由于我们的递推是由 $i$ 推向 $i+1$ ,那么只考虑什么时候 $i$ 推移会引起补偿花费增加
设某个村 $j$ 左右最远的能将其覆盖的村分别为 $st[j], ed[j]$ ,那么也就是当 $ed[j]=i$ 时当 $i$ 向后推会造成 $cost(k,i)$ 增加 $W[j]$ ,其中 $k<st[j]$ ,显然这样的 $k$ 是从 $1$ 开始的连续的一段,于是可以用一颗线段树维护区间最小值
用链表将 $ed=i$ 的 $j$ 全部挂在 $i$ 下面,当 $i$ 往后推时扫一遍链表中的 $j$ ,将线段树中区间 $[1,st[j])$ 全部加上 $W[j]$
线段树区间修改区间查询就行

代码

#define MAX_N 40007
#define INF 2e9

int N, K;
int st[MAX_N], ed[MAX_N];
ll D[MAX_N], S[MAX_N], C[MAX_N], W[MAX_N];
ll f[2][MAX_N], mn[MAX_N * 4], tag[MAX_N * 4], res;
std::vector<int> hor[MAX_N];

inline void input () {
    read(N), read(K);
    for (int i = 2; i <= N; ++i)
        read(D[i]);
    for (int i = 1; i <= N; ++i)
        read(C[i]);
    for (int i = 1; i <= N; ++i)
        read(S[i]);
    for (int i = 1; i <= N; ++i)
        read(W[i]);
}

inline void init () {
    D[++N] = INF, W[N] = INF, ++K;
    for (int i = 1; i <= N; ++i) {
        st[i] = std::lower_bound(D + 1, D + N + 1, D[i] - S[i]) - D;
        ed[i] = std::lower_bound(D + 1, D + N + 1, D[i] + S[i]) - D;
        if (D[ed[i]] > D[i] + S[i]) --ed[i];
        hor[ed[i]].push_back(i);
    }
}

inline void update (int x) {
    mn[x] = std::min(mn[x << 1], mn[x << 1 | 1]);
}

inline void pushdown (int x) {
    if (tag[x]) {
        mn[x << 1] += tag[x], tag[x << 1] += tag[x];
        mn[x << 1 | 1] += tag[x], tag[x << 1 | 1] += tag[x];
        tag[x] = 0;
    }
}

void build (int x, int l, int r) {
    if (l > r) return;
    tag[x] = 0;
    if (l == r) {
        mn[x] = f[0][l];
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    update(x);
}

ll query (int x, int l, int r, int ql, int qr) {
    if (l > r || ql > qr || l > qr || ql > r) return INF;
    if (ql <= l && r <= qr)
        return mn[x];
    pushdown(x);
    int mid = l + r >> 1;
    ll ans = INF;
    if (ql <= mid) ans = std::min(ans, query(x << 1, l, mid, ql, qr));
    if (mid < qr) ans = std::min(ans, query(x << 1 | 1, mid + 1, r, ql, qr));
    return ans;
}

void modify (int x, int l, int r, int ql, int qr, ll val) {
    if (l > r || ql > qr || l > qr || ql > r) return;
    if (ql <= l && r <= qr) {
        mn[x] += val;
        tag[x] += val;
        return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    if (ql <= mid) modify(x << 1, l, mid, ql, qr, val);
    if (mid < qr) modify(x << 1 | 1, mid + 1, r, ql, qr, val);
    update(x);
}

inline void solve () {
    ll w = 0;
    for (int i = 1; i <= N; ++i) {
        f[0][i] = w + C[i];
        for (int j = 0, end = hor[i].size(); j < end; ++j)
            w += W[hor[i][j]];
    }
    res = f[0][N];
    for (int i = 2; i <= K; ++i) {
        build(1, 1, N);
        for (int j = 1; j <= N; ++j) {
            f[1][j] = query(1, 1, N, 1, j - 1) + C[j];
            for (int k = 0, end = hor[j].size(); k < end; ++k) {
                modify(1, 1, N, 1, st[hor[j][k]] - 1, W[hor[j][k]]);
            }
        }
        memcpy(f[0], f[1], sizeof(f[0]));
        res = std::min(res, f[1][N]);
    }
    printf("%lld\n", res);
}

int main () {
    input();
    init();
    solve();
    return 0;
}

引用资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注