神题啊，好吧，应该是因为我太弱了。。。
设f[i][k]表示到第i个村庄,第i个村庄一定会建基站,已经建了k个基站的最小费用.
f[i][k]=min{f[j][k-1]+cost(j+1,i-1)}+c[i];
//注意本题线段树维护的是当我们枚举i的时候，线段树来维护f【j】【k-1】+cost【j】【i】，就是之前的值和中间的值，整体维护dp方程中的东西。同时在枚举i增加的过程中，维护cost【j】【i】（此时的i已经++了），也就是根据题目的性质，改变cost【j】【i】的值，进而改变方程的值，都是在线段树中处理，提取的时候就跳到前面的那个步骤了
cost(x,y)表示x到y这一段的最小补偿费用.这个dp是O(n^3)的,TLE.
由于状态数已经是N^2,主要的瓶颈在于转移的复杂度cost(x,y)的计算.考虑y增加对solve(x,y)的影响.
原来被左端点覆盖的没有影响,被右端点覆盖的会减少并且不会再被覆盖.
考虑用线段树优化这个dp.用线段树维护f[x]+
cost(x+1,y)的最小值.
设bg[x],ed[x]表示在[bg[x],ed[x]]范围内建造基站村庄x能被覆盖.
每次处理完x位置,枚举所有r[a]=x的村庄a（邻接表）,然后在线段树中把[1,bg[a]-1]都加上w[a].
因为a村庄已经无法被右端点覆盖,所以这些当做左端点也无法覆盖a的村庄的f+cost值肯定要增加w[a];
枚举k,每次都要重新建树.我们可以把n和k加1,这样每次最优值都储存在f[n]中
实际上本题的本质就是，写出dp方程，用线段树来维护dp中的数据，并且高效的进行区间更新，查找最值
这道题思路是并不难理解，但是代码实现确实有一些技巧，刚开始我就写不出来啊，细节详见注释
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; int n,k; ll f[200005],dis[200005],c[200005],w[200005],s[200005]; int ed[200005],bg[200005]; int tot,head[200005],pre[200005],to[200005]; void addedge(int x,int y) { to[++tot]=y;pre[tot]=head[x];head[x]=tot; } struct aa { int l,r; ll mi,add; }a[200005<<2]; void up(int i) { a[i].mi=inf;//注意。下面要min，这里就应该先设为无穷大 if (a[i<<1].l) a[i].mi=min(a[i<<1].mi,a[i].mi);//注意a【i<<1】.l，只有下面有节点才更新，否则会有0的情况 if (a[i<<1|1].l) a[i].mi=min(a[i<<1|1].mi,a[i].mi); } void down(int i) { if (a[i].add) { a[i<<1].add+=a[i].add; a[i<<1|1].add+=a[i].add; a[i<<1].mi+=a[i].add; a[i<<1|1].mi+=a[i].add; a[i].add=0; } } void build(int i,int l,int r) { a[i].l=l;a[i].r=r; a[i].add=a[i].mi=0; if (l==r) { a[i].mi=f[l];//刚开始把所有的上一次计算的答案加进去 return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); up(i); } void add(int i,int l,int r,ll x) { if (l>r) return ;//防止出现l>r,特殊情况的处理 if (a[i].l==l&&a[i].r==r) { a[i].mi+=x; a[i].add+=x; return ; } down(i); int mid=(a[i].l+a[i].r)>>1; if (mid>=r) add(i<<1,l,r,x); else if (mid<l) add(i<<1|1,l,r,x); else add(i<<1,l,mid,x),add(i<<1|1,mid+1,r,x); up(i); } ll query(int i,int l,int r) { if (l>r) return 0; if (a[i].l==l&&a[i].r==r) return a[i].mi; int mid=(a[i].l+a[i].r)>>1; down(i); if (mid>=r) return query(i<<1,l,r); else if (mid<l) return query(i<<1|1,l,r); return min(query(i<<1,l,mid),query(i<<1|1,mid+1,r)); } void init() { scanf("%d%d",&n,&k); for (int i=2;i<=n;i++) scanf("%lld",&dis[i]); for (int i=1;i<=n;i++) scanf("%lld",&c[i]); for (int i=1;i<=n;i++) scanf("%lld",&s[i]); for (int i=1;i<=n;i++) scanf("%lld",&w[i]); n++;k++; dis[n]=w[n]=inf;//有距离，保证不影响答案 ，这里因为f【n】【k】表示在第n个建总共k个的最小值，但是最优答案不一定是在n这个位置建，所以n++，通过分析保证n+1的值不会影响答案，主要是dis【n+1】要大于dis【n】 for (int i=1;i<=n;i++) { bg[i]=lower_bound(dis+1,dis+i+1,dis[i]-s[i])-dis; ed[i]=upper_bound(dis+i,dis+n+1,dis[i]+s[i])-dis-1; addedge(ed[i],i);//邻接表 } } int main() { init(); ll tmp=0; for (int i=1;i<=n;i++)//初始计算边界，f【i】【1】，前i个数选1个 { f[i]=c[i]+tmp; for (int l=head[i];l;l=pre[l]) tmp+=w[to[l]];//因为前边不可能选，所以这里没有选到就是没有选到了 } ll ans=f[n]; for (int j=2;j<=k;j++) { build(1,1,n);//循环队列，这一次的状态只与上一次有关，所以用上一次的f数组来建线段树 memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) { f[i]=query(1,1,i-1)+c[i];//query询问1~i-1的最小值 for (int l=head[i];l;l=pre[l]) { int x=to[l]; add(1,1,bg[x]-1,w[x]);//在之前的cost都要增加 } } ans=min(ans,f[n]);//因为是至多k个，所以可以选不到k个 } printf("%lld",ans); return 0; }
