线段树优化dp
数组f[i][j]表示在前i个村庄内，第j个基站建在i处的最小费用
根据交线牛逼法和王鹤松式可得方程
f[i][j]=min(f[k][j−1]+cost(k,i))
cost(k,i)表示第i~k个村庄之间没有被基站覆盖的村庄所需的赔偿费用，计算费用的复杂度为O(n)
利用二分查找预处理每个位置的需求范围bef[i],beh[i]
之后就是利用线段树维护f[]+cost()的最小值，区间查询区间更新
当beh[x]=i,若i不建造，则加cost(可能存在很多x，前向星或vector存储)
Code:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define ls(k) k<<1
#define rs(k) k<<1|1
using namespace std;
const int N=20010,K=110;
int dis[N],s[N],w[N],c[N],f[N];
int n,m,bef[N],beh[N];
int tot=0,to[N<<1],head[N<<1],nxt[N<<1];
int mn[N<<2],lz[N<<2];
void Add(int x,int y)
{to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
void up(int k)
{mn[k]=min(mn[ls(k)],mn[rs(k)]);
}
void build(int k,int l,int r)
{lz[k]=0;if(l==r){mn[k]=f[l];return ;}int mid=l+r>>1;build(ls(k),l,mid);build(rs(k),mid+1,r);up(k);
}
void down(int k)
{lz[ls(k)]+=lz[k];lz[rs(k)]+=lz[k];mn[ls(k)]+=lz[k];mn[rs(k)]+=lz[k];lz[k]=0;
}
int query(int k,int l,int r,int L,int R)
{if(L>R)return 0x3f3f3f3f;if(L<=l&&R>=r)return mn[k];int mid=l+r>>1;if(lz[k])down(k);int res=0x3f3f3f3f;if(L<=mid)res=min(res,query(ls(k),l,mid,L,R));if(mid<R)res=min(res,query(rs(k),mid+1,r,L,R));return res;
}
void change(int k,int l,int r,int L,int R,int vl)
{if(L>R)return ;if(L<=l&&R>=r){lz[k]+=vl;mn[k]+=vl;return ;}if(lz[k])down(k);int mid=l+r>>1;if(L<=mid)change(ls(k),l,mid,L,R,vl);if(R>mid)change(rs(k),mid+1,r,L,R,vl);up(k);
}
int main()
{scanf("%d%d",&n,&m);for(int i=2;i<=n;i++)scanf("%d",&dis[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]);n++,m++;dis[n]=w[n]=0x3f3f3f3f;for(int i=1;i<=n;i++){bef[i]=lower_bound(dis+1,dis+n+1,dis[i]-s[i])-dis;beh[i]=lower_bound(dis+1,dis+n+1,dis[i]+s[i])-dis;if(dis[beh[i]]>dis[i]+s[i])beh[i]--;Add(beh[i],i);}int now=0;for(int j=1;j<=n;j++){f[j]=now+c[j];for(int i=head[j];i;i=nxt[i])now+=w[to[i]];}int ans=f[n];for(int i=2;i<=m;i++){build(1,1,n);for(int j=1;j<=n;j++){f[j]=query(1,1,n,1,j-1)+c[j];for(int p=head[j];p;p=nxt[p])change(1,1,n,1,bef[to[p]]-1,w[to[p]]);}ans=min(ans,f[n]);}cout<<ans<<endl;return 0;
}