BZOJ 1835 [ZJOI2010]base 基站选址:线段树优化dp

时间:2024-08-03 20:33:14

传送门

题意

有 $ n $ 个村庄在一排直线上,现在要建造不超过 $ K $ 个通讯基站,基站只能造在村庄处。

第 $ i $ 个村庄距离第 $ 1 $ 个村庄的距离为 $ D_i $ 。在此建造基站的费用为 $ C_i $ 。如果在此不超过 $ S_i $ 的范围内有基站,那么这个村庄就被覆盖了。如果它没有被覆盖,则需要花费 $ W_i $ 的补偿费用。

问你最小总花费是多少。

题解

首先有一个很显然的dp:

$ dp[i][j] $ 表示在第 $ i $ 个村庄建了基站,此时一共建了 $ j $ 个基站,第 $ i $ 个以及之前村庄的最小花费。

转移为:

\[dp[i][j] = min(dp[k][j-1] + cost(k,i)) \quad (k<i)
\]

其中 $ cost(k,i) $ 表示如果在 $ k $ 和 $ i $ 建了基站,并且它们之间没有建基站,此时村庄 $ k $ 到村庄 $ i $ 之间的花费,即:

\[cost(i,j) = \sum_{k=i}^j W_k * [|D_k-D_i|>S_k \text{ } \& \text{ } |D_k-D_j|>S_k]
\]

然后考虑如何优化。

先定义 $ l_i $ 和 $ r_i $ 分别表示能够覆盖村庄 $ i $ 的最左和最右的基站建造位置,可以直接二分出来。

我们希望对于每个 $ j $ 来说,在 $ i $ 不断递增的过程中,动态地维护 $ F(k) = dp[k][j-1] + cost(k,i) $ 的最小值。

假设当前已经求出了 $ dp[i-1][j] $ ,接下来该求 $ dp[i][j] $ 了。

那么对于所有满足 $ r_p = i-1 $ 的 $ p $ 来说,所有 $ F(k) \quad (k \in [1,l_p-1]) $ 都应该加上 $ W_p $ 。也就是将基站从 $ i-1 $ 移动到 $ i $ 之后,给对应的 $ F(k) $ 加上了那些本来被覆盖但是现在不覆盖的村庄的补偿费。

所以对于当前的 $ i ​$ 来说,$ dp[i][j] = min(F(k)) \quad (k \in [1,i-1]) ​$

由于有区间加法和查区间最小值,所以要用线段树维护 $ F(k) $ 。对于每个 $ j $ 来说,在一开始重建一下线段树就好。

AC Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 20005
#define MAX_V 80005
#define INF 1000000000
#define int long long using namespace std; int n,K,ans;
int d[MAX_N];
int c[MAX_N];
int s[MAX_N];
int w[MAX_N];
int l[MAX_N];
int r[MAX_N];
int dp[MAX_N];
int dat[MAX_V];
int tag[MAX_V];
vector<int> v[MAX_N]; void read()
{
scanf("%lld%lld",&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++;
} void cal_lr()
{
for(int i=1;i<=n;i++)
{
l[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
r[i]=upper_bound(d+1,d+1+n,d[i]+s[i])-d-1;
v[r[i]].push_back(i);
}
} void push_down(int k)
{
if(tag[k])
{
dat[k*2+1]+=tag[k];
dat[k*2+2]+=tag[k];
tag[k*2+1]+=tag[k];
tag[k*2+2]+=tag[k];
tag[k]=0;
}
} void push_up(int k)
{
dat[k]=min(dat[k*2+1],dat[k*2+2]);
} void build(int l,int r,int k)
{
if(l==r)
{
dat[k]=dp[l];
tag[k]=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,k*2+1);
build(mid+1,r,k*2+2);
push_up(k);
tag[k]=0;
} void update(int a,int b,int k,int l,int r,int x)
{
if(a<=l && r<=b)
{
dat[k]+=x;
tag[k]+=x;
return;
}
push_down(k);
int mid=(l+r)>>1;
if(a<=mid) update(a,b,k*2+1,l,mid,x);
if(b>mid) update(a,b,k*2+2,mid+1,r,x);
push_up(k);
} int query(int a,int b,int k,int l,int r)
{
if(a<=l && r<=b) return dat[k];
push_down(k);
int mid=(l+r)>>1,ans=INF;
if(a<=mid) ans=min(ans,query(a,b,k*2+1,l,mid));
if(b>mid) ans=min(ans,query(a,b,k*2+2,mid+1,r));
return ans;
} void cal_dp()
{
int sum=0;
for(int i=1;i<=n;i++)
{
dp[i]=sum+c[i];
for(int j=0;j<v[i].size();j++) sum+=w[v[i][j]];
}
ans=dp[n];
for(int j=2;j<=K;j++)
{
build(1,n,0);
for(int i=1;i<=n;i++)
{
if(i>1) dp[i]=query(1,i-1,0,1,n)+c[i];
else dp[i]=c[i];
for(int k=0;k<v[i].size();k++)
{
int t=v[i][k];
if(l[t]>1) update(1,l[t]-1,0,1,n,w[t]);
}
}
ans=min(ans,dp[n]);
}
} void work()
{
cal_lr();
cal_dp();
printf("%lld\n",ans);
} signed main()
{
read();
work();
}