40%的数据中，N<=500； 100%的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。
1.lazy标记打错了，应该是 += ，不能直接覆盖 2.lc<<1 打成了 >>1 ，调了半天 3.优化思路：首先是每个村庄的左右端点，二分查找并记录 DP方程 f[i][j]=min(f[k][j-1]+pay[x])+c[i],表示第 j 个基站建在第 i 个村庄时的最小花费，不考虑 i+1 到 n 显然，可以去掉一维 f[i]=min(f[i]+pay[x])+c[i]; 此时，考虑优化计算 pay[x] ，也就是没有被覆盖的点的花费 因为若 ed[x]=i,此时 i 不被选择，那么 计算 i+1 时就要加上花费 所以，我们应维护一个区间，存储上一个基站建在 i 时的最小花费之和 ，即 f[k][j-1]+pay[x]; 在计算时，查找 [1,i-1]的最小值 然后更新所有以 i 为右端点的村庄的花费，区间为 [1,st[x]-1]; 最后，因为我们考虑的是当前点对前面的影响，所以我们在最后新建一个假点，用来保存结果
个人总结：把线段树当成一种工具，可以快速存储，查找想要的值，利用这一特性我们有规律地存储我们想要的值。可达到大大节约时间的目的
代码：
#include<bits/stdc++.h>
#define re register int
#define int long long
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int N=2e4+10;
const int INF=1e12+7;
int n,k,tot,num;
int dis[N],c[N],s[N],w[N],st[N],ed[N];
struct TREE
{
int zh,lazy;
}use[N*40];
long long f[N];
int to[N<<1],next[N<<1],head[N<<1];
void add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
void pp(int p)
{
use[p].zh=min(use[lc].zh,use[rc].zh);
}
void pd(int p)
{
if(!use[p].lazy)
return;
use[lc].lazy+=use[p].lazy;
use[rc].lazy+=use[p].lazy;
use[lc].zh+=use[p].lazy;
use[rc].zh+=use[p].lazy;
use[p].lazy=0;
}
void build(int p,int l,int r)
{
use[p].lazy=0;
if(l==r)
{
use[p].zh=f[l];
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pp(p);
}
int query(int p,int L,int R,int l,int r)
{
if(l>r)
return INF;
if(l<=L&&R<=r)
return use[p].zh;
int mid=(L+R)>>1;
int ans=INF;
pd(p);
if(l<=mid)
ans=min(ans,query(lc,L,mid,l,r));
if(mid<r)
ans=min(ans,query(rc,mid+1,R,l,r));
return ans;
}
void change(int p,int L,int R,int l,int r,int z)
{
if(l>r)
return;
if(l<=L&&R<=r)
{
use[p].zh+=z;
use[p].lazy+=z;
return;
}
int mid=(L+R)>>1;
pd(p);
if(l<=mid)
change(lc,L,mid,l,r,z);
if(mid<r)
change(rc,mid+1,R,l,r,z);
pp(p);
}
signed main()
{
scanf("%lld%lld",&n,&k);
for(re i=2;i<=n;i++)
scanf("%lld",&dis[i]);
for(re i=1;i<=n;i++)
scanf("%lld",&c[i]);
for(re i=1;i<=n;i++)
scanf("%lld",&s[i]);
for(re i=1;i<=n;i++)
scanf("%lld",&w[i]);
++n;
++k;
dis[n]=INF;
w[n]=INF;
for(re i=1;i<=n;i++)
{
st[i]=lower_bound(dis+1,dis+n+1,max(dis[i]-s[i],0*1ll))-dis;
ed[i]=upper_bound(dis+1,dis+n+1,min(dis[i]+s[i],dis[n]))-dis;
ed[i]-=1;
add(ed[i],i);
}
int sum=0;
for(re i=1;i<=n;i++)
{
f[i]=sum+c[i];
for(re j=head[i];j;j=next[j])
sum+=w[to[j]];
}
int out=f[n];
for(re i=2;i<=k;i++)
{
build(1,1,n);
for(re j=1;j<=n;j++)
{
f[j]=query(1,1,n,1,j-1)+c[j];
for(re k=head[j];k;k=next[k])
{
int p=to[k];
change(1,1,n,1,st[p]-1,w[p]);
}
}
out=min(out,f[n]);
}
printf("%lld\n",out);
}
