先考虑朴素dp,设\(f_{i,j}\)表示在第\(i\)个村庄放了基站,一共放了\(j\)次,且只考虑前面村庄影响的答案.这里可以把\(j\)放在外面枚举,然后从\(f_{k,j-1}(k<i)\)转移到\(f_{i,j}\)
这里对于每个村庄,能影响它的基站是在一个区间里的,我们先二分找出能影响到它的最左边以及最右边基站位置.然后转移的时候还要考虑一些没被覆盖的村庄的代价,对于\(x\)村庄,如果\(k<L_x\)并且\(i>R_x\),那么要加上\(w_x\)的代价.考虑优化此过程,我们把\(f_{k,j-1}\)的贡献放在以\(k\)为下标的线段树上,每次取前缀最大值转移.然后如果处理完当前的\(i\),然后有些村庄的\(R_x=i\),那么以后的转移放的基站都不能直接覆盖\(x\)了,那么从\(<L_x\)转移过来的基站都要加上\(w_x\)的代价,线段树区间加即可.然后贡献答案是要加上后面没被覆盖的村庄代价
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db doubleusing namespace std;
const int N=20000+10;
const LL inf=1ll<<40;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,kk,d[N],p[N][2];
LL f[2][N],dt[N],ans,c[N],w[N];
vector<int> op[N],ad[N];
vector<int>::iterator it;
LL mi[N<<2],tg[N<<2];
void add(int o,LL x){mi[o]+=x,tg[o]+=x;}
void psdn(int o){if(tg[o]) add(o<<1,tg[o]),add(o<<1|1,tg[o]),tg[o]=0;}
void psup(int o){mi[o]=min(mi[o<<1],mi[o<<1|1]);}
void modifc(int o,int l,int r,int lx,LL x)
{
if(l==r){mi[o]=x;return;}
psdn(o);
int mid=(l+r)>>1;
if(lx<=mid) modifc(o<<1,l,mid,lx,x);
else modifc(o<<1|1,mid+1,r,lx,x);
psup(o);
}
void modifa(int o,int l,int r,int ll,int rr,LL x)
{
if(ll<=l&&r<=rr){add(o,x);return;}
psdn(o);
int mid=(l+r)>>1;
if(ll<=mid) modifa(o<<1,l,mid,ll,rr,x);
if(rr>mid) modifa(o<<1|1,mid+1,r,ll,rr,x);
psup(o);
}
LL quer(int o,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr) return mi[o];
psdn(o);
LL an=inf,mid=(l+r)>>1;
if(ll<=mid) an=min(an,quer(o<<1,l,mid,ll,rr));
if(rr>mid) an=min(an,quer(o<<1|1,mid+1,r,ll,rr));
psup(o);
return an;
}int main()
{
n=rd(),kk=rd();
for(int i=2;i<=n;++i) d[i]=rd();
for(int i=1;i<=n;++i) c[i]=rd();
for(int i=1;i<=n;++i)
{
int x=rd();
p[i][0]=i;
int l=1,r=i-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(d[i]-d[mid]<=x) p[i][0]=mid,r=mid-1;
else l=mid+1;
}
p[i][1]=i;
l=i+1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(d[mid]-d[i]<=x) p[i][1]=mid,l=mid+1;
else r=mid-1;
}
ad[p[i][0]].push_back(i);
op[p[i][1]].push_back(i);
}
int nw=1,la=0;
for(int i=0;i<=n;++i) f[0][i]=f[1][i]=inf;
f[la][0]=0;
for(int i=1;i<=n;++i)
{
w[i]=rd();
ans+=w[i];
}
for(int i=n,dd=0;i;--i)
{
dt[i]=dd;
for(it=ad[i].begin();it!=ad[i].end();++it) dd+=w[*it];
}
while(kk--)
{
modifc(1,0,n,0,f[la][0]);
for(int i=1;i<=n;++i)
{
f[nw][i]=quer(1,0,n,0,i-1)+c[i];
ans=min(ans,f[nw][i]+dt[i]);
modifc(1,0,n,i,f[la][i]);
for(it=op[i].begin();it!=op[i].end();++it) modifa(1,0,n,0,p[*it][0]-1,w[*it]);
}
for(int i=0;i<=n;++i) f[la][i]=inf;
nw^=1,la^=1;
}
printf("%lld\n",ans);
return 0;
}
