简单题
设(f_{i,j})表示选择了(i)个关键点，最后一个关键点选择的位置是(j)，([1,j])的最小代价。
显然(f_{i,j}=min(f_{i-1,k}+w(k+1,j)),k<j)，(w(i,j))为区间(i,j)左边/右边放置基站的代价函数。
由于我们知道当前这一段左/右最近的点，所以代价可以在(O(n))的时间内扫描计算。
时间复杂度为(O(n^3k))。
考虑优化，把点分成2类。
如果当前点(x)距离(ileq s_x)，则是(1)类点，费用为(0)。
否则是(2)类点，当左边放置基站位置离(jleq s_x)，费用为(0)，否则费用为(W_j)。
当(k)往左移动时，每个点的类型不会变化。
而二类点能够产生代价贡献的(k)是区间，可以通过二分预处理。
可以差分维护代价。
时间复杂度变为(O(n^2k))。
考虑继续优化，对(f_{i-1})建立一颗线段树。
当(j)向右移动时，一些一类点可能变为二类点。
预处理出每个点变成二类点时(j)的位置。
这时这些点就会对区间产生贡献。
可以使用区间加法/(min)维护。
这需要我们求出一个点(i)左边/右边第一个距离(>s_i)的位置，可以二分。
时间复杂度变为(O(knlog_2n))
#include<bits/stdc++.h>
using namespace std;
#define int long long
using namespace std;
#define N 100010
int n,k,f[120][N],tg[N],mn[N],d[N],c[N],s[N],w[N],a[N],l[N],r[N];
struct no{
int l,r,v;
};
vector<no>g[N];
void bd(int o,int l,int r){
if(l==r){
mn[o]=a[l];
return;
}
int md=(l+r)/2;
bd(o*2,l,md);
bd(o*2+1,md+1,r);
mn[o]=min(mn[o*2],mn[o*2+1]);
}
void pd(int o){
if(tg[o]){
tg[o*2]+=tg[o];
tg[o*2+1]+=tg[o];
mn[o*2]+=tg[o];
mn[o*2+1]+=tg[o];
tg[o]=0;
}
}
void ad(int o,int l,int r,int x,int y,int z){
if(r<x||y<l)
return;
if(x<=l&&r<=y){
tg[o]+=z;
mn[o]+=z;
return;
}
pd(o);
int md=(l+r)/2;
ad(o*2,l,md,x,y,z);
ad(o*2+1,md+1,r,x,y,z);
mn[o]=min(mn[o*2],mn[o*2+1]);
}
int qu(int o,int l,int r,int x,int y){
if(r<x||y<l)
return 1e18;
if(x<=l&&r<=y)
return mn[o];
pd(o);
int md=(l+r)/2;
return min(qu(o*2,l,md,x,y),qu(o*2+1,md+1,r,x,y));
}
int e1(int p,int s){
int l=p,r=n+1,ans=n+1;
while(l<=r){
int md=(l+r)/2;
if(d[md]-d[p]>s){
ans=md;
r=md-1;
}
else
l=md+1;
}
return ans;
}
int e2(int p,int s){
int l=0,r=p,ans=0;
while(l<=r){
int md=(l+r)/2;
if(d[p]-d[md]>s){
ans=md;
l=md+1;
}
else
r=md-1;
}
return ans;
}
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=2;i<=n;i++)
scanf("%lld",&d[i]);
d[0]=-1e16;
d[n+1]=1e16;
for(int i=1;i<=n;i++)
scanf("%lld",&c[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&s[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
for(int i=0;i<=n;i++){
r[i]=e1(i,s[i]);
l[i]=e2(i,s[i]);
g[r[i]].push_back((no){0,l[i],w[i]});
}
memset(f,32,sizeof(f));
f[0][0]=0;
for(int i=0;i<=k;i++){
memset(tg,0,sizeof(tg));
memset(mn,0,sizeof(mn));
for(int j=0;j<=n+1;j++)
a[j]=f[i][j];
bd(1,0,n+1);
for(int j=1;j<=n+1;j++){
for(int l=0;l<g[j].size();l++){
no x=g[j][l];
ad(1,0,n+1,x.l,x.r,x.v);
}
f[i+1][j]=qu(1,0,n+1,0,j-1)+c[j];
}
}
int ans=1e17;
for(int i=0;i<=k+2;i++)
ans=min(ans,f[i][n+1]);
printf("%lld",ans);
}