【LG2605】[ZJOI2010]基站选址

【LG2605】[ZJOI2010]基站选址

题面

洛谷

题解

先考虑一下暴力怎么写，设\(f_{i,j}\)表示当前\(dp\)到\(i\)，且强制选\(i\)，目前共放置\(j\)个的方案数。

那么转移为\(f_{i,j}=\min_{k=1}^{i-1} \{f_{k,j-1}+cost_{k,i}\}+c_i\)，其中\(cost_{l,r}\)表示\([l,r]\)只选两端中间的补偿。

其中\(cost\)只需要\(O(\frac {n^3}4)\)预处理就好了，那么复杂度为\(O(\frac {n^3}4+kn^2)\)。

考虑优化这个暴力，此时我们只需要对于\(f_{i,j}\)找到满足条件的最小的\(k\)即可。

而对于一个位置\(i\)，它要贡献\(w_i\)当且仅当一段区间内没有建基站，这个可以二分出来。

我们对这些按右端点区间排个序，那么可以知道过了某个位置\(i\)，对于右端点在\(i\)的所有区间的左端点\(l\)，区间\([1,l-1]\)内的\(f\)值必然会增加，那么用线段树维护区间取\(\min\)及区间加法即可。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <climits> 
using namespace std;

inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
    if (ch == '-') w = -1 , ch = getchar();
    while (ch >= '0' && ch <= '9') data = (data << 1) + (data << 3) + (ch ^ 48), ch = getchar();
    return w * data;
}
#define MAX_N 20005 
int N, K;
int D[MAX_N], C[MAX_N], S[MAX_N], W[MAX_N];
int dp[MAX_N]; 
struct Line {
    int l, r;
    bool operator < (const Line & rhs) const {
        return r < rhs.r; 
    }
} p[MAX_N];
vector<int> vec[MAX_N];
#define lson (o << 1)
#define rson (o << 1 | 1)
int addv[MAX_N << 2], minv[MAX_N << 2];
void pushup(int o) { minv[o] = min(minv[lson], minv[rson]); }
void puttag(int o, int w) { minv[o] += w, addv[o] += w; }
void pushdown(int o) {
    puttag(lson, addv[o]);
    puttag(rson, addv[o]);
    addv[o] = 0; 
}
void build(int o, int l, int r) {
    addv[o] = 0;
    if (l == r) {
        minv[o] = dp[l];
        return ; 
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(o); 
}
void modify(int o, int l, int r, int ql, int qr, int w) { 
    if (ql > qr) return ;
    if (ql <= l && r <= qr) {
        puttag(o, w);
        return ; 
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(lson, l, mid, ql, qr, w);
    if (qr > mid) modify(rson, mid + 1, r, ql, qr, w);
    pushup(o); 
}
int query(int o, int l, int r, int ql, int qr) {  
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return minv[o];
    pushdown(o);
    int mid = (l + r) >> 1, res = INT_MAX;
    if (ql <= mid) res = min(res, query(lson, l, mid, ql, qr));
    if (qr > mid) res = min(res, query(rson, mid + 1, r, ql, qr));
    return res; 
}
int main () {
    N = gi(), K = gi();
    for (int i = 2; i <= N; i++) D[i] = gi();
    for (int i = 1; i <= N; i++) C[i] = gi();
    for (int i = 1; i <= N; i++) S[i] = gi(); 
    for (int i = 1; i <= N; i++) W[i] = gi();
    for (int i = 1, l, r, pos = 1; i <= N; i++) {
        l = 1, r = i - 1, pos = i;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (D[i] - D[mid] <= S[i]) pos = mid, r = mid - 1;
            else l = mid + 1; 
        }
        p[i].l = pos;
        l = i + 1, r = N, pos = i;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (D[mid] - D[i] <= S[i]) pos = mid, l = mid + 1;
            else r = mid - 1; 
        }
        p[i].r = pos; 
    }
    for (int i = 1; i <= N; i++) vec[p[i].r].push_back(i); 
    for (int i = 1, tmp = 0; i <= N + 1; i++) {
        dp[i] = tmp + C[i];
        for (int j = 0; j < vec[i].size(); j++)
            tmp += W[vec[i][j]]; 
    }
    int ans = dp[N + 1]; 
    for (int i = 1; i <= K; i++) { 
        build(1, 1, N + 1); 
        for (int j = 1; j <= N + 1; j++) { 
            dp[j] = query(1, 1, N + 1, 1, j - 1) + C[j]; 
            for (int k = 0; k < vec[j].size(); ++k) { 
                modify(1, 1, N + 1, 1, p[vec[j][k]].l - 1, W[vec[j][k]]); 
            }
        }
        ans = min(ans, dp[N + 1]); 
    }
    printf("%d\n", ans); 
    return 0; 
}