Luogu

分析

设 $dp_{i,j}$ 表示建了 $i$ 个基站，最后一个建在 $j$ 时只考虑 $1\sim j$ 的最小代价。

这样子最后会有一段没有算，所以我们在最后再加一个村庄 $n+1$，然后答案就是所有 $dp_{i,n+1}$ 的最小值。

考虑转移。枚举上一个建站的位置可以得到
$$
dp_{i,j}=\min_{p}\left\{dp_{i-1,p}+cost(p,j)\right\}
$$
这里的 $cost(p,j)$ 表示 $[p,j]$ 中只有 $p$ 和 $j$ 建了基站时会产生多少的补偿费。

考虑优化。先二分出每个村庄最左、最右的能够覆盖到它的村庄 $L_i$ 和 $R_i$。那么如果 $[L_i,R_i]$ 内没有基站，就会产生 $w_i$ 的补偿费。

也就是说，对于每个 $R<j$ 的村庄 $p$，它会给所有的 $cost(i,j)\,(i<L_p)$ 加上 $w_p$。

那么我们就可以线段树优化 DP 了，每次转移就查一下区间最小值，然后对于每个 $R_p=j$ 的村庄 $p$ 做一次 $1\sim L_i-1$ 的区间加即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000+10;

int n,k;
int d[N],c[N],s[N],w[N];
int L[N],R[N]; vector<int> vec[N];
int dp[N];

#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2],addv[N<<2];
inline void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
inline void pushdown(int o) {
    if (addv[o]) {
        minv[ls]+=addv[o],addv[ls]+=addv[o];
        minv[rs]+=addv[o],addv[rs]+=addv[o];
        addv[o]=0;
    }
}
inline 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(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql>qr) return;
    if (ql<=l&&r<=qr) { minv[o]+=w,addv[o]+=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline 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];
    int mid=(l+r)>>1,res=2e9; pushdown(o);
    if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
    pushup(o); return res;
}
#undef ls
#undef rs

int main() {
    n=read(),k=read();
    for (re int i=2;i<=n;++i) d[i]=read();
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<=n;++i) s[i]=read();
    for (re int i=1;i<=n;++i) w[i]=read();
    for (re int i=1;i<=n;++i) {
        L[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
        R[i]=upper_bound(d+1,d+n+1,d[i]+s[i])-d-1;
        vec[R[i]].push_back(i);
    }
    for (re int i=1,s=0;i<=n+1;++i) {
        dp[i]=s+c[i];
        for (re int j:vec[i]) s+=w[j];
    }
    int ans=dp[n+1];
    for (re int i=2;i<=k;++i) {
        build(1,1,n+1);
        for (re int j=1;j<=n+1;++j) {
            dp[j]=query(1,1,n+1,1,j-1)+c[j];
            for (re int p:vec[j]) modify(1,1,n+1,1,L[p]-1,w[p]);
        }
        ans=min(ans,dp[n+1]);
    }
    printf("%d\n",ans);
    return 0;
}