题意：有 \(n\) 个点，告诉你每个点距离第一个点的距离，需要在 \(n\) 个点中选择出 \(K\) 个关键点，选这个点作为关键点代价为 \(W_i\)。现在还有代价， \(S_i\) 表示如果距离 \(i\) 在 \(S_i\) 以内的点存在一个关键点，那么这个点就被覆盖了，不产生代价。选完 \(K\) 个关键点之后，如果存在第 \(i\) 个点没被覆盖就会产生 \(W_i\) 的额外代价。求最小化代价。
题看错了一次（ \(S_i\) 那里 ）。这种题还要多练。
首先 \(dp[i][j]\) 表示前 \(i\) 个点选了 \(j\) 个点作为关键点，强制选 \(i\) 的最小代价。
转移随便，发现有个 \(cost(k+1,i-1 )\) 这个代价函数，表示的是这段区间内没被覆盖的点的总额外代价。记得滚掉一维。直觉判断 \(cost\) 函数不能硬维护。首先发现每个点所代表的区间左右延伸的最后一个点能够处理，那么我 DP 的时候选择的上一个点在 \([1,l-1]\) 的话显然就需要加上 \(W_i\) 的代价，所以只需要做一个区间加就行了，然后求 \(dp[i]\) 就是前缀 \(\min\) 。所以说我先转移 \(dp\) ，然后我做一个扫描，扫到这个点，我就判断它是哪些区间的右端点，并把这些区间的 \([1,l-1]\) 区间加 \(W_i\) 。
值得注意的是，我们最后转移 \(dp[n]\) 的时候，我们是强制选 \(n\) ，但是可以不选，所以搞个虚拟点，统计答案就行。
#include<bits/stdc++.h>
#define int long long
#define MAXN 30005
const int inf=1e18;
int gi(){
char c;int x=0,f=0;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))x=(x*10)+(c^48),c=getchar();
return f?-x:x;
}
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
int n,K,d[MAXN],c[MAXN],s[MAXN],w[MAXN],dp[MAXN],l[MAXN];
std::vector<int>g[MAXN];
namespace segtree{
#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1)
int sum[MAXN<<2],tag[MAXN<<2];
void up(int x){sum[x]=std::min(sum[ls],sum[rs]);}
void addtag(int x,int l,int r,int w){sum[x]+=w,tag[x]+=w;}
void down(int x,int l,int r){
if(!tag[x])return;
addtag(ls,l,mid,tag[x]),addtag(rs,mid+1,r,tag[x]);
tag[x]=0;
}
void build(int x,int l,int r){
tag[x]=0;
if(l==r)return sum[x]=dp[l],void();
build(ls,l,mid),build(rs,mid+1,r);
up(x);
}
void upd(int x,int l,int r,int L,int R,int w){
if(l>R||r<L)return;
if(L<=l&&r<=R)return addtag(x,l,r,w);
down(x,l,r);
upd(ls,l,mid,L,R,w),upd(rs,mid+1,r,L,R,w);
up(x);
}
int query(int x,int l,int r,int L,int R){
if(l>R||r<L)return inf;
if(L<=l&&r<=R)return sum[x];
down(x,l,r);
return std::min(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
#undef ls
#undef rs
#undef mid
}
using namespace segtree;
int find(int x,int i){
int lt=0,rt=n+1,pos=i;
while(lt+1<rt){
int mid=(lt+rt)>>1;
if(x<=d[mid])rt=mid,pos=mid;
else lt=mid;
}
return pos;
}
int find2(int x,int i){
int lt=0,rt=n+1,pos=i;
while(lt+1<rt){
int mid=(lt+rt)>>1;
if(d[mid]<=x)lt=mid,pos=mid;
else rt=mid;
}
return pos;
}
void DP(){
int ans=inf,os=0;
for(int i=1;i<=n;i++){
dp[i]=c[i];
for(int j=1;j<i;j++){
if(d[j]-s[j]<=d[i]&&d[i]<=d[j]+s[j])continue;
dp[i]+=w[j];
}
}
ans=dp[n];
for(int k=2;k<=K;k++){
build(1,1,n);
for(int i=1;i<=n;i++){
dp[i]=query(1,1,n,1,i-1)+c[i];if(i==1)dp[1]=c[i];
for(int v:g[i])if(v>=2)upd(1,1,n,1,l[v]-1,w[v]);
}
ans=std::min(ans,dp[n]);
}
printf("%lld\n",ans);
}
signed 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(); //补偿费用
++n,++K,d[n]=w[n]=inf,c[n]=0;
for(int i=1;i<=n;i++)g[find2(d[i]+s[i],i)].emplace_back(i),l[i]=find(d[i]-s[i],i);
DP();
return 0;
}