bzoj 1835 [ZJOI2010]基站选址
内容
题目描述
有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。
输入输出格式
输入格式：
输入文件的第一行包含两个整数N,K，含义如上所述。
第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。
第三行包含N个整数，表示C1,C2,…CN。
第四行包含N个整数，表示S1,S2,…,SN。
第五行包含N个整数，表示W1,W2,…,WN。
输出格式：
输出文件中仅包含一个整数，表示最小的总费用。
输入输出样例
输入样例#1：
3 2
1 2
2 3 2
1 1 0
10 20 30
输出样例#1：
4
说明
40%的数据中，N<=500；
100%的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。
题解：
动态规划+线段树优化的一道好题
以下设c[i]是i村庄建立基站的费用，w[i]是i村庄没被覆盖的补偿费用
定义状态
$f(i,j)$表示前j个村子建立了i个基站且第i个基站建立于j号村子的费用(包括前j个村的建站费和补偿费)
先写出朴素DP的方程：$f(i,j)=min \{ f(i-1,k)+cost(k,j) \} +c(j)$,其中$1<=k<=j-1$，$cost(k,j)$是只在k和j两点修建基站，对于两点中间村庄的补偿费用
其中第i层的状态只和第i-1层相关，可以降维成$f(i)=min \{ f(j)+cost(j,i) \} +c(i),1<=j<=i-1$
可是我们发现，计算$cost(j,i)$是一个$O(n^3)$的过程，效率过低
那么现在的问题就是如何维护$cost$
优化
我们假设$f(j)$目前已经计算完了，现在想要计算$f(j+1)$
我们转移每一层$(1 \sim K)$时，建立一棵线段树，对于每个点k维护$f(k)+cost(k,j)$(注意这个东西是随着j的增长而变化的)
观察一下方程，可以发现，原方程中每个$f(k),1<=k<=j-1$是不随着j的增长而变化的，变化的只有$cost(k,i)$
是什么引起了$cost(k,i)$的变化呢?从$cost(k,i)$变化到$cost(k,i+1)$,说明有些本来能被i位置建立的一座基站覆盖到的村子，因为$i->i+1$而覆盖不到了，需要给他们补偿
那么我们可以预处理出每个村庄的$l$和$r$，分别代表在村庄i左(右)侧建立基站仍能覆盖到村庄i的最远村庄位置，这个可以二分求出，$O(nlogn)$
每次转移完$f(i)$时，将$r(x)=i$的所有x，将$[1,l[x]-1]$这段区间在线段树中加上$w[x]$即可
细节处理
实际实现的时候我们发现每层的答案并不一定是$f(n)$，因为最后一个基站不一定建立在最后一个村庄
那么我们开始的时候$++n$和$++K$，在最后添加一个距离正无穷，建站费用为0，补偿费用为正无穷的村子
这样之后$f(n)$就一定是答案了
#include <cstdio>
#include <algorithm>
#define inf 0x3f3f3f3f
#define N 200003
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int inline read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct edge
{
int to,next;
}e[N];
int n,m;
int s[N],c[N],d[N],l[N],r[N],tot,w[N],f[N];
int st[N],mins[N*4],mark[N*4];
void add(int x,int y)
{
e[++tot].to=y;
e[tot].next=st[x];
st[x]=tot;
}
void pushup(int rt)
{
mins[rt]=min(mins[rt<<1],mins[rt<<1|1]);
}
void build(int rt,int l,int r)
{
mark[rt]=0;
if (l==r)
{
mins[rt]=f[l];
return;
}
int mid=l+r>>1;
build(lson);
build(rson);
pushup(rt);
}
void pushdown(int rt)
{
if (mark[rt])
{
mark[rt<<1]+=mark[rt];
mark[rt<<1|1]+=mark[rt];
mins[rt<<1]+=mark[rt];
mins[rt<<1|1]+=mark[rt];
mark[rt]=0;
}
}
int query(int rt,int l,int r,int L,int R)
{
if (l>=L && r<=R)
return mins[rt];
pushdown(rt);
int mid=l+r>>1,ans=inf;
if (mid>=L)
ans=min(ans,query(lson,L,R));
if (mid<R)
ans=min(ans,query(rson,L,R));
return ans;
}
void update(int rt,int l,int r,int L,int R,int x)
{
if (l>=L && r<=R)
mins[rt]+=x,mark[rt]+=x;
else
{
pushdown(rt);
int mid=l+r>>1;
if (mid>=L)
update(lson,L,R,x);
if (mid<R)
update(rson,L,R,x);
pushup(rt);
}
}
main()
{
scanf("%d%d",&n,&m);
for (int i=2;i<=n;i++)
d[i]=read();
for (int i=1;i<=n;i++)
c[i]=read();
for (int i=1;i<=n;i++)
s[i]=read();
for (int i=1;i<=n;i++)
w[i]=read();
d[n+1]=inf; w[n+1]=inf; s[n+1]=inf; n++; m++;
for (int i=1;i<=n;i++)
{
l[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
r[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d;
if (d[r[i]]>d[i]+s[i]) r[i]--;
add(r[i],i);
}
int ans=inf,t=0;
for (int i=1;i<=n;i++)
{
f[i]=t+c[i];
for (int j=st[i];j;j=e[j].next)
t+=w[e[j].to];
}
ans=min(ans,f[n]);
for (int i=2;i<=m;i++)
{
build(1,1,n);
for (int j=1;j<=n;j++)
{
if (j==1) f[j]=c[j];
else f[j]=query(1,1,n,1,j-1)+c[j];
for (int k=st[j];k;k=e[k].next)
if (l[e[k].to]-1>=1)
update(1,1,n,1,l[e[k].to]-1,w[e[k].to]);
}
ans=min(ans,f[n]);
}
printf("%d\n",ans);
}