洛谷2605:基站选址
题意描述:
- 有(N)个村庄在一条直线上，第(i(i>1))个村庄的距离第(1)个村庄的距离为(D_i)。
- 需要在这些村庄中建立不超过(K)个通讯站，在第(i)个村庄建立基站的费用为(C_i)。
- 如果在距离第(i)个村庄不超过(S_i)的范围内建立了一个通讯站，那么村庄就被基站覆盖。
- 如果第(i)个村庄没有被覆盖，则要向他们补偿，费用为(W_i)。
- 现在的问题是，选择基站的位置，使得总花费最小。
- 数据范围：
- (kleq N,kleq 100,Nleq2*10^4,D_ileq 10^9,C_ileq 10^4,S_ileq 10^9, w_ileq 10^4)。
输入格式：
- 第一行包含两个整数(N,K)，含义如上所述。
- 第二行包含(N-1)个整数，分别表示(D_2,D_3,...,D_n)(()与第一个村庄的距离())，这(N-1)个数是递增的。
- 第三行输入(N)个整数，表示(C_1,C_2,...,C_n)(()在第(i)个村庄建基站的费用())。
- 第四行输入(N)个整数，表示(S_1,S_2,...,S_n)(()第(i)个基站覆盖的距离())。
- 第五行输入(N)个整数，表示(W_1,W_2,...,W_n)(()表示补偿的费用())
输出格式：
- 输出一个整数表示最小的总费用。
思路：
-
线段树优化(dp)。
-
先考虑最朴素的(dp)如何处理。
-
设(f(i,j))表示表示前(i)个村庄建立了(j)个通讯站的最小开销。为了方便转移，让第(j)个通讯站强制建立在第(i)个位置。
-
有状态转移方程：(f(i,j)=min(f(k,j-1)+cost(k,i))+C_i)。
-
也可以滚动一下变成(f(i)=min(f(k)+cost(k,i))+c_i)。
- 多设立一个空节点(n+1)。
- 那么最后的答案就是(ans=min(f(n+1,i))(1leq ileq k+1))。
-
其中(cost(k,i))表示从第(k)到第(i)个村庄选择外其他的都不选，所需要的补偿的费用。
- 计算(cost)的时间复杂度为(O(n))。
- 计算(dp)的时间复杂度为(O(nk))，所以总时间复杂度为(O(n^2k))。
-
这个复杂度显然是无法通过的，对于枚举(i,j)而言，无法降低复杂度。我们可以在计算(cost)上下功夫。
-
对于每一个村庄(i)，都需要在一个范围内建基站，否则就要做出赔偿。假设第(i)个基站的区间是([l_i,r_i])。
-
考虑在不在(r)处建立基站，有如下两种可能：
- (1:)不在(r)处建立基站，那么对于当前村庄(i)来说，上一个基站在([1,l-1])这个区间的话，就要对(i)村庄进行赔偿。那么我们就需要在([1,l-1])区间加上村庄(i)的赔偿费用。
- (2:)在(r)处建立基站，那么就要查询区间最小值了。
-
为了维护如上两个操作(快速区间修改，求区间最小值)，我们可以采用线段树。
-
所以转移过程中用线段树维护(min(f(k,j)+cost(k,i)))即可。
-
当然还需要开两个数组辅助：
- (st(i))表示第(i)个村庄的左端点(l_i)。
- (ed(i))表示第(i)个村庄的右端点(r_i)。
-
当然也会有很多点的(ed)都为(i)，所以用前向星来存一下。
-
时间复杂度被优化到了(O(knlogn))，大约在(10^7)左右，可以通过。
代码：
#include<bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
typedef long long ll;
const int maxn = 2e4 + 10;
const ll INF = 1e18 + 10;
int n, k;
int st[maxn], ed[maxn];
ll c[maxn], w[maxn], d[maxn], s[maxn];
ll f[maxn], ans;
int head[maxn], nex[maxn<<1], ver[maxn<<1], tot;
void add_edge(int x, int y){
ver[++tot] = y; nex[tot] = head[x]; head[x] = tot;
}
struct SegmentTree
{
int l, r, add;
ll dat;
#define lson (p<<1)
#define rson (p<<1|1)
#define l(x) tree[x].l
#define r(x) tree[x].r
#define dat(x) tree[x].dat
#define add(x) tree[x].add
}tree[maxn<<2];
inline void pushup(int p){
dat(p) = min(dat(lson), dat(rson));
}
inline void spread(int p)
{
if(add(p))
{
dat(lson) += add(p);
dat(rson) += add(p);
add(lson) += add(p);
add(rson) += add(p);
add(p) = 0;
}
}
void build(int p, int l, int r)
{
add(p) = 0;
l(p) = l, r(p) = r;
if(l == r)
{
dat(p) = f[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid+1, r);
pushup(p);
}
ll ask(int p, int l, int r)
{
if(l <= l(p) && r(p) <= r) return dat(p);
spread(p);
int mid = (l(p) + r(p)) >> 1;
ll val = INF;
if(l <= mid) val = min(val, ask(lson, l, r));
if(mid < r) val = min(val, ask(rson, l, r));
return val;
}
void change(int p, int l, int r, int d)
{
if(l <= l(p) && r(p) <= r)
{
dat(p) += (ll)d;
add(p) += d;
return;
}
spread(p);
int mid = (l(p)+r(p)) >> 1;
if(l <= mid) change(lson, l, r, d);
if(mid < r) change(rson, l, r, d);
pushup(p);
}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 2; i <= n; i++) scanf("%lld", &d[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]);
d[++n] = INF, w[n] = INF; k++;
//建立虚节点
//预处理出区间
for(int i = 1; i <= n; i++)
{
st[i] = lower_bound(d+1, d+1+n, d[i]-s[i])-d;
ed[i] = lower_bound(d+1, d+1+n, d[i]+s[i])-d;
if(d[ed[i]] > d[i] + s[i]) ed[i] -= 1;
add_edge(ed[i], i);
}
//开始dp
ans = INF; int t = 0;
for(int i = 1; i <= k; i++)
{
if(i == 1) //预处理出只有一个基站的答案
{
t = 0;
for(int j = 1; j <= n; j++)
{
f[j] = t + c[j];
//寻找恰好被j覆盖 但不被j+1覆盖掉的点
for(int p = head[j]; p; p = nex[p])
{
int v = ver[p];
t += w[v];
}
}
ans = f[n]; continue;
}
//f(i)每次都在变 所以每次都更新一下线段树
build(1, 1, n);
for(int j = 1; j <= n; j++)
{
if(j == 1) f[j] = c[j];
else f[j] = ask(1, 1, j-1) + c[j]; //建立基站
//不建立基站
//将赔偿金累加到线段树中去
for(int p = head[j]; p; p = nex[p])
{
int v = ver[p];
if(st[v] - 1 > 0)
change(1, 1, st[v]-1, w[v]);
}
}
//更新答案
ans = min(ans, f[n]);
}
printf("%lld
", ans);
return 0;
}