题意
有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为(D_i)
需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为(C_i)
如果在距离第i个村庄不超过(S_i)的范围内建立了一个通讯基站，那么就成它被覆盖了
如果第i个村庄没有被覆盖，则需要向他们补偿，费用为(W_i)
现在的问题是，选择基站的位置，使得总费用最小。
分析
朴素做法
用(f(i,j))表示前(i)个村庄建了(j)个通讯站且第(j)个建在(i)处的最小代价，容易写出转移式
其中(cost(k,i))表示中间的补偿费用
然而这种做法时间是(O(N cdot K cdot N))，空间是(O(N^2))的，不可行。
优化
如果我们外层枚举(j)，里面枚举(i)呢？
很显然(f)的第二维和(cost)的第一维都可以省略。(f)可以用滚动，(cost)可以动态更新，因为变化元素的其实是有限（均摊(O(1))）的。
由于一个村庄(i)被覆盖的条件是在距离第(i)个村庄不超过(S_i)的范围内建立了一个通讯基站，因此可以发现能覆盖一个村庄的基站位置应该是一个区间。
考虑第(i)个村庄对于的区间([L,R])，如果目前考虑的最后一个基站为(R)，要转移到(R+1)
- 如果(R)处不建基站，那么对于相对(R+1)的上一个基站为([1,L-1])的情况，都无法覆盖当前村庄，因此需要对(cost)的([1,L-1])区间加(W_i)
- 如果(R)处建基站，那么相当于是在相对(R+1)的上一个基站为([1,R-1])中选择一个代价最小的，相当于对之前(f)和(cost)的和区间查询最小值
用程序的语言来讲，我们用(st_i)和(ed_i)分别表示(i)最左端、最右端可以覆盖到(i)的通讯站位置，那么我们会发现当(ed_x=i)时，转移到(i+1)时(x)便覆盖不到了。
我们用线段树维护(min{f(k)+cost(k)})，从(f(i))变到(f(i+1))时对于(ed_x=i)的(x),线段树中([1,st_x−1])都加上(W_x)(加上补偿费用)即可
这样(f)就不用滚动了，(cost)也不用单独提出来。
外层循环枚举建站个数时每次重建线段树，复杂度(O(K cdot N log N))
代码
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2e4+7;
#define lson (o<<1)
#define rson (o<<1|1)
int d[MAXN],c[MAXN],s[MAXN],w[MAXN];
int st[MAXN],ed[MAXN];
vector<int> g[MAXN];
int f[MAXN],ans;
struct SegTree
{
int minv[MAXN<<2],addv[MAXN<<2]; // edit 3
void pushup(int o)
{
minv[o]=min(minv[lson],minv[rson]);
}
void build(int o,int l,int r)
{
addv[o]=0; // edit 2
if(l==r)
{
minv[o]=f[l];
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(o);
}
void pushdown(int o)
{
if(addv[o])
{
minv[lson]+=addv[o],addv[lson]+=addv[o];
minv[rson]+=addv[o],addv[rson]+=addv[o];
addv[o]=0;
}
}
int qmin(int o,int l,int r,int ql,int qr)
{
if(ql>qr)
return 0;
// cerr<<"query "<<o<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
if(ql<=l&&r<=qr)
return minv[o];
pushdown(o);
int mid=(l+r)>>1,ans=INF;
if(ql<=mid)
ans=min(ans,qmin(lson,l,mid,ql,qr));
if(qr>=mid+1)
ans=min(ans,qmin(rson,mid+1,r,ql,qr));
return ans;
}
void add(int o,int l,int r,int ql,int qr,int v)
{
if(ql>qr)
return;
// cerr<<"add "<<o<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<v<<endl;
if(ql<=l&&r<=qr)
{
minv[o]+=v,addv[o]+=v;
return;
}
pushdown(o);
int mid=(l+r)>>1;
if(ql<=mid)
add(lson,l,mid,ql,qr,v);
if(qr>=mid+1)
add(rson,mid+1,r,ql,qr,v);
pushup(o);
}
}T;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n,m;
read(n);read(m);
for(int i=2;i<=n;++i)
read(d[i]);
for(int i=1;i<=n;++i)
read(c[i]);
for(int i=1;i<=n;++i)
read(s[i]);
for(int i=1;i<=n;++i)
read(w[i]);
d[++n]=INF,w[n]=INF,++m;
for(int i=1;i<=n;++i)
{
st[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
ed[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d;
if(d[ed[i]]>d[i]+s[i])
--ed[i];
g[ed[i]].push_back(i);
}
int t=0;
for(int i=1;i<=n;++i)
{
f[i]=t+c[i];
for(int j=0;j<g[i].size();++j)
{
int x=g[i][j];
t+=w[x];
}
}
ans=f[n];
for(int i=2;i<=m;++i)
{
T.build(1,1,n); // edit 1
for(int j=1;j<=n;++j)
{
f[j]=T.qmin(1,1,n,1,j-1)+c[j];
for(int k=0;k<g[j].size();++k)
{
int x=g[j][k];
T.add(1,1,n,1,st[x]-1,w[x]);
}
}
ans=min(ans,f[n]);
}
printf("%d
",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}