可以很容易的写出dp方程：
F[i][j]=min(F[l][j-1]+w[l][i])+c[i] (w[i][j]是从l+1到i-1这些点p里，所有满足d[p]+s[p]<d[i] && d[p]-s[p]>d[l]的点的w[p]之和)
考虑i+1，会对方程造成什么变化
w[l][i]会变得跟大了（满足d[p]+s[p]<d[i]的点更多了）
可以发现增长的是一个区间，求和也是一个区间
线段树解决
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 20100
#define inf 1000000000
struct node {
int l,r,mi,lz;
}t[maxn*8];
#define lc(x) (x<<1)
#define rc(x) ((x<<1)+1)
#define mi(x) t[x].mi
#define lz(x) t[x].lz
#define mid ((l+r)>>1)
#define update(x) mi(x)=min(mi(lc(x)),mi(rc(x)))
int f[maxn],pf[maxn];
int build(int x,int l,int r) {
t[x].l=l,t[x].r=r;
t[x].lz=0;
if (l==r) return t[x].mi=pf[l];
build(lc(x),l,mid);
build(rc(x),mid+1,r);
update(x);
return 0;
}
int pushback(int x) {
if (t[x].l==t[x].r) return 0;
lz(lc(x))+=lz(x),lz(rc(x))+=lz(x);
mi(lc(x))+=lz(x),mi(rc(x))+=lz(x);
lz(x)=0;
}
int query(int x,int x1,int y1){
int l=t[x].l,r=t[x].r;
if (y1<l||x1>r) return inf;
if (x1<=l&&y1<=r) return mi(x);
pushback(x);
return min(query(lc(x),x1,y1),query(rc(x),x1,y1));
}
int add(int x,int x1,int y1,int z) {
int l=t[x].l,r=t[x].r;
if (y1<l||x1>r) return 0;
if (x1<=l&&y1>=r) return lz(x)+=z,mi(x)+=z;
pushback(x);
add(lc(x),x1,y1,z),add(rc(x),x1,y1,z);
update(x);
}
int n,k;
int c[maxn],s[maxn],d[maxn],w[maxn];
int st[maxn],ed[maxn];
vector<int> list[maxn];
int solve(){
int sum=0;
for (int i=1;i<=n;i++) {
f[i]=sum+c[i];
for(int j=0;j<list[i].size();j++) sum+=w[list[i][j]];
}
int ans=f[n];
for (int i=1;i<=k;i++) {
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
memcpy(pf,f,sizeof(pf));
for (int j=1;j<=n;j++) f[j]=inf;
build(1,1,n);
for (int j=1;j<=n;j++){
f[j]=min(f[j],query(1,1,j-1))+c[j];
for (int k=0;k<list[j].size();k++) add(1,1,st[list[j][k]]-1,w[list[j][k]]);
}
ans=min(ans,f[n]);
}
printf("%d\n",ans);
return 0;
}
int main(){
scanf("%d%d",&n,&k);
for (int i=2;i<=n;i++) scanf("%d",d+i);
for (int i=1;i<=n;i++) scanf("%d",c+i);
for (int i=1;i<=n;i++) scanf("%d",s+i);
for (int i=1;i<=n;i++) scanf("%d",w+i);
d[++n]=inf,c[n]=w[n]=s[n]=0;
for (int i=1;i<=n;i++) {
st[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
ed[i]=upper_bound(d+1,d+1+n,d[i]+s[i])-d-1;
list[ed[i]].push_back(i);
}
solve();
return 0;
}
