看一眼题目，变知道这题一定是dp
设f[i][j]表示在第i个村庄修建第j个基站且不考虑i+1~n个村庄的最小费用
可以得出f[i][j] = Min(f[k][j - 1] + cost[k][i] ) + c[i] (j - 1 <= k < i)
其中cost[k][i]表示i~k之间没有基站所需要的费用
计算复杂度O(N)，加上循环，总复杂度O(N^2 K)
看一下数据范围K <= N，K <= 100 , N <= 20000
真棒，TLE
考虑如何优化
首先，我们发现之前的转移方程可以去掉一维j，实际上只要在最外层枚举j就可以了
f[i] = Min( f[k] + cost[k][i] ) + c[i] (j - 1 <= k < i)
主要的时间浪费在计算cost上
我们要找方法来优化
对于任意一个村庄i，记它所能被覆盖的左右边界st[i],ed[i]（最左端、最右端可以覆盖到i的基站位置，可用二分查找处理）
然后在用邻接表记录ed值为i的村庄有哪些，在这些村庄之前建立基站就覆盖不到i了。
这样当我们推导i + 1时，若从村庄1~st[k] - 1(ed[k] = i)转移过来则必定要赔偿村庄k的费用，我们就可以考虑用线段树来维护f[k] + cost[k][i]的值
即在区间[1, st[k] - 1]加上村庄k的费用，而转移即在区间[1, i - 1]找f[k] + cost[k][i]的最小值，总复杂度为O(N log N K)。
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define N 20005
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int Min(register int a,register int b)
{
return a<b?a:b;
}
int D[N],C[N],S[N],W[N],lr[N],rr[N],f[N];
vector<int> vq[N];
int ql,qr;
struct Segment_tree{
int minn[N<<2],tag[N<<2];
inline void pushup(register int x)
{
minn[x]=Min(minn[x<<1],minn[x<<1|1]);
}
inline void build(register int x,register int l,register int r)
{
tag[x]=0;
if(l==r)
{
minn[x]=f[l];
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
inline void maintain(register int x,register int l,register int r)
{
if(l!=r)
pushup(x);
minn[x]+=tag[x];
}
inline void update(register int x,register int l,register int r,register int v)
{
if(ql<=l&&qr>=r)
tag[x]+=v;
else
{
int mid=(l+r)>>1;
if(ql<=mid)
update(x<<1,l,mid,v);
if(qr>mid)
update(x<<1|1,mid+1,r,v);
}
maintain(x,l,r);
}
inline int query(register int x,register int l,register int r,register int v)
{
if(ql<=l&&qr>=r)
return minn[x]+v;
int ret=inf,mid=(l+r)>>1;
if(ql<=mid)
ret=Min(ret,query(x<<1,l,mid,v+tag[x]));
if(qr>mid)
ret=Min(ret,query(x<<1|1,mid+1,r,v+tag[x]));
return ret;
}
}T;
int main()
{
int n=read(),k=read();
for(register int i=2;i<=n;++i)
D[i]=read();
for(register int i=1;i<=n;++i)
C[i]=read();
for(register int i=1;i<=n;++i)
S[i]=read();
for(register int i=1;i<=n;++i)
W[i]=read();
++n,++k;
D[n]=inf;
for(register int i=1;i<=n;++i)
{
lr[i]=lower_bound(D+1,D+n+1,D[i]-S[i])-D;
rr[i]=lower_bound(D+1,D+n+1,D[i]+S[i])-D;
if(D[i]+S[i]<D[rr[i]])
--rr[i];
vq[rr[i]].push_back(i);
}
int ans=inf;
for(register int j=1;j<=k;++j)
{
if(j==1)
{
int tot=0;
for(register int i=1;i<=n;++i)
{
f[i]=tot+C[i];
for(register int tmp=0;tmp<vq[i].size();++tmp)
tot+=W[vq[i][tmp]];
}
ans=Min(ans,f[n]);
continue;
}
T.build(1,1,n);
for(register int i=1;i<=n;++i)
{
ql=1,qr=i-1;
int add=qr?T.query(1,1,n,0):0;
f[i]=add+C[i];
for(register int tmp=0;tmp<vq[i].size();++tmp)
{
ql=1,qr=lr[vq[i][tmp]]-1;
if(qr>0)
T.update(1,1,n,W[vq[i][tmp]]);
}
}
ans=Min(ans,f[n]);
}
printf("%d",ans);
return 0;
}