LuoguP2605 [ZJOI2010]基站选址 题解
Description
题目链接
有 N 个村庄坐落在一条直线上，第 i(i>1)1 个村庄的距离为 D_i。需要在这些村庄中建立不超过 K 个通讯基站，在第 i 个村庄建立基站的费用为 C_i。如果在距离第 i 个村庄不超过 S_i 的范围内建立了一个通讯基站，那么村庄就被通讯信号覆盖。如果第 i 个村庄没有被通讯信号覆盖，则需要向他们补偿，费用为 W_i。现在的问题是，选择基站的位置，使得总费用最小。
求出最小的总费用。
1leq N leq 2times 10^4,1leq K leq 100。
Solution
首先很容易就可以列出一个暴力 DP 方程：
设 dp[i][j] 表示前 i 个村庄，造 j 个通讯基站的最小花费。
很显然，这题的瓶颈主要在求解 cost[k,i] 上。
我们可以令 st[i] 表示如果在村庄 i 造基站，向左最多能覆盖到哪个村庄，ed[i] 表示向右最多能覆盖到哪个村庄。
考虑用线段树维护下 min{dp[k][j-1] cost[k,i]}
我们每次更新 dp[i][j] 时，可以把 ed[k] 刚好为 i 的 k 的 [1,st[k]-1] 的 cost 全部加上 w[k]（代表这些村庄需要补偿）。
因为所有后面的点，如果要从 [1,st[k]-1] 的点转移过来，k 必定无法被覆盖到，所以要加上赔偿费用。
然后更新的时候直接取用 [1,j-1] 的最小值即可。
最后可以在无穷远处开个费用为 0 的点，便于统计答案。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=20010;
int n,m,d[N],c[N],s[N],w[N],inf=2e9,f[N],tr[N<<2],tag[N<<2],st[N],ed[N];
vector<int> v[N];
#define IT vector<int>::iterator
#define LW(x) lower_bound(d 1,d n 1,x)-d
#define mid (l r>>1)
#define ls x<<1,l,mid
#define rs x<<11,mid 1,r
#define UP(x) tr[x]=min(tr[x<<1],tr[x<<11])
#define PD(x) tag[x]&&(Add(x<<1,tag[x]),Add(x<<11,tag[x]),tag[x]=0)
IT It;
I void Add(CI x,CI val){tr[x] =val;tag[x] =val;return ;}
I void build(CI x,CI l,CI r){if(tag[x]=0,l==r) return void(tr[x]=f[l]);build(ls),build(rs),UP(x);}
I void update(CI x,CI l,CI r,CI L,CI R,CI val){if(L>R) return ;if(L<=l&&r<=R) return Add(x,val);PD(x);if(L<=mid) update(ls,L,R,val);if(R>mid) update(rs,L,R,val);UP(x);}
I int query(CI x,CI l,CI r,CI L,CI R){if(L>R) return inf;if(L<=l&&r<=R) return tr[x];PD(x);RI res=inf;if(L<=mid) res=min(res,query(ls,L,R));if(R>mid) res=min(res,query(rs,L,R));return res;}
int main(){
RI i,j,S;read(n,m);for(d[1]=0,i=2;i<=n;i ) read(d[i]);for(i=1;i<=n;i ) read(c[i]);for(i=1;i<=n;i ) read(s[i]);for(i=1;i<=n;i ) read(w[i]); m, n,d[n]=w[n]=inf;
for(i=1;i<=n;i ) st[i]=LW(d[i]-s[i]),ed[i]=LW(d[i] s[i]),d[ed[i]]>d[i] s[i]&&ed[i]--,v[ed[i]].push_back(i);for(S=0,i=1;i<=n;i ) for(f[i]=S c[i],It=v[i].begin();It!=v[i].end();It ) S =w[*It];
for(S=f[n],i=2;i<=m;S=min(S,f[n]),i ) for(build(1,1,n),j=1;j<=n;j ) for(f[j]=query(1,1,n,1,j-1) c[j],It=v[j].begin();It!=v[j].end();It ) update(1,1,n,1,st[*It]-1,w[*It]);return writeln(S),0;
}
