P2605 [ZJOI2010]基站选址解题思路

解题思路

数据结构优化 $dp$
前置知识：线段树区间修改 / 区间求最小值 + $dp$

看到本题，我们首先要想最暴力的状态设置以及转移方程式。
令 $dp[i][j]$ 表示在第 $i$ 个村庄建设第 $j$ 个基站同时 只考虑 前 $i$ 个村庄的最小费用。

ps.这里的"只考虑"指的是只计算前 $i$ 个村庄的补偿款或者建设基站的费用。

不难想到状态转移方程：

$dp[i][j] = min(dp[k][j - 1] + calc(k,i) (j - 1 <= k < i))$

$calc(k,i)$ 表示的是第 $k + 1$ 个村庄到第 $i - 1$ 个村庄都不修建基站的补偿费用。

这样子的空间复杂度是:O $(nk)$ 的，时间复杂度是 o( $n^2k$ ) 的，显然通过不了本题。

我们可以优化这个 $dp$ 过程。

首先最简单的就是优化空间（其实优化不优化都能通过本题。~~不过作为一名Oier，这你能忍？~~

考虑到我们用的只有 $dp[i][j]$ 以及 $dp[i][j - 1]$ ，用滚动数组优化即可。

优化后的状态转移方程：

$dp[i] = min(dp[k] + calc(k,i))$

不难发现时间复杂度瓶颈在于计算 $calc(k,i)$ ，这个我们每次都需要遍历一次才能知道 $calc(k,i)$

有没有办法动态更新？有的。

不妨设：

$L[i]$ 表示最左边能够覆盖村庄 $i$ 的基站。
$R[i]$ 表示最右边能够覆盖村庄 $i$ 的基站。

这两个都可以在 $nlogn$ 的时间内用二分的方法预处理出来。

观察到我们的 $i$ 在进行状态转移的时候只会不停的右移，不断变成 $i + 1$ , $i + 2$ .......

这个 $i$ 右移影响到了什么呢？可以发现：

假设有一个村庄 $k$ , $i = R[k]$ ,我们不在 $i$ 村庄修建基站的话，那么为了不给村庄 $k$ 补偿款，则必须在区间 $[L[k], R[k] - 1]$ 修建基站，那么假设上一个修建基站的位置是在 $[1, L[k]]$ 之间的话，就必须提供补偿款。

也就是说，假如我们现在在进行 $dp[i][j]$ 的状态转移，倘若 $i$ 没有修基站，有一些(注意不是一个),姑且称之为村庄 $t$ , 村庄 $t$ 的 $R[t]$ 是在 $i$ ,相当于要给 $1 <= k < L[t] - 1$ 现在的 $calc(k, i + 1), calc(k, i + 2) ....$ 加上 $W[t]$ ,因为上一个建立基站的位置 $k < L[t]$ ，并且下一个建设基站的位置大于 $R[t]$ ，所以说就得付补偿款 $W[t]$ ，考虑到要动态修改一段区间，所以采用 线段树。

转移的话，线段树里面区间取 $min(dp[k] + calc(k,i))$ 即可 (线段树里面存的值是 $dp[k] + calc(k,i)$ )。

复杂度: O( $nlogn$ * $k$ )

最后的一个小 $trick$ 就是开一个超级点，令其 $S[i] = 0, C[i] = 0, D[i] = INF, W[i] = INF$

那么这个超级点在最后就一定会被选择修建基站但是不影响答案，这个点就设置为第 $n + 1$ 个点就行了，然后 $n ++$ , $K ++$ ，可以帮助我们更好的统计答案。

Code

#include <bits/stdc++.h>
using namespace std;
#define mid ((L[x] + R[x]) >> 1)
#define int long long
inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}
const int MAXN = 2e4 + 50;
int n, K, tot = 0;
int D[MAXN], C[MAXN], S[MAXN], W[MAXN], st[MAXN], ed[MAXN], start[MAXN];
int dp[MAXN];

struct Edge {
    int next,to;
} edge[MAXN << 1];

struct SegmentTree {
    int Min[MAXN << 2], laz[MAXN << 2], L[MAXN << 2], R[MAXN << 2];
    void build(int x, int l, int r) {
        L[x] = l, R[x] = r; laz[x] = 0;
        if(l == r) {Min[x] = dp[l]; return ;}
        build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r);
        Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
        return ;
    }
    void ad(int x,int k) {Min[x] += k, laz[x] += k; return ;}
    void pushdown(int x) {
        if(laz[x] == 0) return ;
        ad(x << 1 , laz[x]); ad(x << 1 | 1 , laz[x]);
        laz[x] = 0;
        return ;
    }
    void change(int x,int l,int r,int k) {
        if(l > r) return ;
        if(L[x] >= l && R[x] <= r) {ad(x, k); return ;}
        pushdown(x);
        if(l <= mid) change(x << 1 , l , r , k);
        if(r  > mid) change(x << 1 | 1 , l , r , k);
        Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
        return ;
    }
    int GetMin(int x, int l, int r) {
        int M = 1e18;
        if(l > r) return 1e18;
        if(L[x] >= l && R[x] <= r) return Min[x];
        pushdown(x);
        if(l <= mid) M = min(GetMin(x << 1, l, r), M);
        if(r  > mid) M = min(GetMin(x << 1 | 1, l, r), M);
        return M;
    }
} T;

void add(int from, int to) {
    edge[++ tot].to = to;
    edge[tot].next = start[from];
    start[from] = tot;
    return ;
}

void Prepare() {
    for(int i = 1; i <= n ; i ++) {
        int L = i, R = i;
        for(int j = log2(i) ; j >= 0 ; j --) {
            int k = L - (1 << j);
            if(k >= 1 && D[i] - D[k] <= S[i]) L = k;
        }
        for(int j = log2(n - i + 1) ; j >= 0 ; j --) {
            int k = R + (1 << j);
            if(k <= n && D[k] - D[i] <= S[i]) R = k;
        }
        st[i] = L, ed[i] = R; add(ed[i], i);
    }
    return ;
}

signed main() {
    n = read(), K = read();
    for(int i = 2 ; i <= n ; i ++) D[i] = read();
    for(int i = 1 ; i <= n ; i ++) C[i] = read();
    for(int i = 1 ; i <= n ; i ++) S[i] = read();
    for(int i = 1 ; i <= n ; i ++) W[i] = read();
    n ++; K ++;
    D[n] = 1e18, W[n] = 1e18, S[n] = 0, C[n] = 0;
    Prepare();
    int now = 0;
    for(int i = 1 ; i <= n ; i ++) {
        dp[i] = now + C[i];
        for(int j = start[i] ; j ; j = edge[j].next) {
            int to = edge[j].to;
            now += W[to];//初始化，因为一开始只能建一个基站，所以会有很多村庄无法覆盖，now要不断的取前缀和。
        }
    }
    int Ans = dp[n];
    for(int j = 2 ; j <= K ; j ++) {
        T.build(1, 1, n);
        for(int i = 1 ; i <= n ; i ++) {
            dp[i] = T.GetMin(1, 1, i - 1) + C[i];
            for(int k = start[i] ; k ; k = edge[k].next) {
                int to = edge[k].to;
                T.change(1, 1, st[to] - 1, W[to]);
            }
        }
        Ans = min(Ans, dp[n]);
    }
    cout << Ans;
    return 0;
}

总结

做了几道数据结构优化 $dp$ 的题目，感觉上来说，都是一个做法：动态更新产生的费用，每次转移后都是要动态的更新新产生的费用。

基站选址这道题对应的是更新 $calc(k,i)$ ，也就是产生的新的无法被覆盖的村庄。

大概感受就是如此。

关于数据结构优化 $dp$ 的好题

推荐练习题：
CF597C Subsequences (偏入门)
CF1389F Bicolored Segments (有点难?)
[USACO05DEC]Cleaning Shifts S (不难)

P2605 [ZJOI2010]基站选址解题思路

解题思路

Code

总结

关于数据结构优化 的好题

关于数据结构优化 $dp$ 的好题