Problem

https://www.luogu.org/problemnew/show/P2605

Solution

考虑 dp 方程。

$$f_{i, j}=\min_{k=1}^{j-1} f_{i-1, k}+cost_{k, j}+c_j$$

$f_{i,j}$ 代表第 $i$ 次建筑时，前 $j$ 个建筑需要支付的最少代价，$j$ 一定为基站。

$cost_{k,j}$ 代表 $k,j$ 之间没有任何基站所需要支付的代价。

考虑 $cost_{k,j}$ 的变化，用线段树维护。

注意滚动数组优化和边界清零。

获取最终答案有两种做法，就是尾部加一个无限远的建筑，或者多加一层循环。因为线段树中包含上一层转移状态，最后在线段树中求 min 等价于放置了一个无限远的建筑，也因此循环次数 +1。

Code

#include<bits/stdc++.h>
using namespace std;

const int N=2e4+10;
int d[N], c[N], s[N], w[N];
int h[N], to[N], W[N], nexp[N], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

#define ls x<<1
#define rs x<<1|1
int mi[N<<3], tag[N<<3];
void pud(int x) {
    if(!tag[x]) return;
    tag[ls]+=tag[x], mi[ls]+=tag[x], tag[rs]+=tag[x], mi[rs]+=tag[x];
    tag[x]=0;
}
void updata(int x, int l, int r, int xl, int xr, int d) {
    pud(x);
    if(xl<=l && r<=xr) { tag[x]+=d, mi[x]+=d; return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, d);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, d);
    mi[x]=min(mi[ls], mi[rs]);
}
int query(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return mi[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return query(ls, l, mid, xl, xr);
    else if(xl>mid) return query(rs, mid+1, r, xl, xr);
    else return min(query(ls, l, mid, xl, mid), query(rs, mid+1, r, mid+1, xr));
}

int f[2][N], cur, lst;
void build(int x, int l, int r) {
    tag[x]=0;
    if(l==r) { mi[x]=f[lst][l]; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    mi[x]=min(mi[ls], mi[rs]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, k, l, r;
    cin>>n>>k;
    for(int i=2;i<=n;i++) cin>>d[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) {
        cin>>w[i];
        l=lower_bound(d+1, d+1+n, d[i]-s[i])-d;
        r=upper_bound(d+1, d+1+n, d[i]+s[i])-1-d;
        ins(r, l-1, w[i]);
    }
    cur=0, lst=1;
    memset(f[cur], 0x3f, sizeof(f[cur]));
    f[cur][0]=0;
    int ans=0x3f3f3f3f;
    for(int i=1;i<=k+1;i++) {
        swap(cur, lst), memset(f[cur], 0x3f, sizeof(f[cur]));
        build(1, 0, n);
        for(int j=1;j<=n;j++) {
            f[cur][j]=query(1, 0, n, 0, j-1)+c[j];
            for(int u=h[j];u;u=nexp[u]) updata(1, 0, n, 0, to[u], W[u]);
        }
        ans=min(ans, mi[1]);
    }
    cout<<ans<<endl;
    return 0;
}