洛谷 P2605 [ZJOI2010] 基站选址

题目来源于：洛谷

题目本质：动态规划dp，线段树

解题思路：f[i][j]表示在第𝑖i个村庄修建第j个基站且不考虑第i+1~n个村庄所需的最小费用。

转移方程为f[i][j]=Min(f[k][j−1]+cst[k][i])+c[i](j−1≤k<i)。其中cst[k][i]表示第i~k个村庄之间没有被基站i,k覆盖的村庄所需的赔偿费用。

代码如下：

#include<bits/stdc++.h>
#define N 20007
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct Edge{int to,nxt;
}edge[N<<2];
struct Tree{int date,mark;
}tr[N<<2];
int n,k,cnt;
int dis[N],val[N],range[N],pay[N],st[N],ed[N],head[N],f[N];
void Add(int u,int v){edge[++cnt]=(Edge){v,head[u]};head[u]=cnt;
}
void Get(){for(int i=1;i<=n;++i){st[i]=lower_bound(dis+1,dis+1+n,dis[i]-range[i])-dis;ed[i]=lower_bound(dis+1,dis+1+n,dis[i]+range[i])-dis;if(dis[ed[i]]>dis[i]+range[i]){--ed[i];}Add(ed[i],i);}
}
void Pushup(int rt){tr[rt].date=min(tr[rt<<1].date,tr[rt<<1|1].date);
}
void Build(int rt,int l,int r){tr[rt].mark=0;if(l==r){tr[rt].date=f[l];return;}int mid=l+((r-l)>>1);Build(rt<<1,l,mid);Build(rt<<1|1,mid+1,r);Pushup(rt);
}
void Pushdown(int rt){if(tr[rt].mark){tr[rt<<1].date+=tr[rt].mark;tr[rt<<1|1].date+=tr[rt].mark;tr[rt<<1].mark+=tr[rt].mark;tr[rt<<1|1].mark+=tr[rt].mark;tr[rt].mark=0;}
}
int Search(int rt,int l,int r,int L,int R){if(L>R){return inf;}if(L<=l&&r<=R){return tr[rt].date;}int mid=l+((r-l)>>1);Pushdown(rt);int num=inf;if(L<=mid){num=min(num,Search(rt<<1,l,mid,L,R));}if(mid<R){num=min(num,Search(rt<<1|1,mid+1,r,L,R));}return num;
}
void Update(int rt,int l,int r,int L,int R,int c){if(L>R){return;}if(L<=l&&r<=R){tr[rt].date+=c;tr[rt].mark+=c;return;}Pushdown(rt);int mid=l+((r-l)>>1);if(L<=mid){Update(rt<<1,l,mid,L,R,c);}if(mid<R){Update(rt<<1|1,mid+1,r,L,R,c);}Pushup(rt);
}
void Dp(){int now=0;for(int j=1;j<=n;++j){f[j]=now+val[j];for(int p=head[j];p;p=edge[p].nxt){int v=edge[p].to;now+=pay[v];}}int ans=f[n];for(int i=2;i<=k;++i){Build(1,1,n);for(int j=1;j<=n;++j){f[j]=Search(1,1,n,1,j-1)+val[j];for(int p=head[j];p;p=edge[p].nxt){int v=edge[p].to;Update(1,1,n,1,st[v]-1,pay[v]);}}ans=min(ans,f[n]);}printf("%lld",ans);
}
void Init(){scanf("%lld%lld",&n,&k);for(int i=2;i<=n;++i){scanf("%lld",&dis[i]);}for(int i=1;i<=n;++i){scanf("%lld",&val[i]);}for(int i=1;i<=n;++i){scanf("%lld",&range[i]);}for(int i=1;i<=n;++i){scanf("%lld",&pay[i]);}++n;++k;dis[n]=pay[n]=inf;
}
signed main(){Init();Get();Dp();return 0;
}