bzoj1835 zjoi2010 base基站选址

bzoj1835 zjoi2010 base基站选址

​​ Description

有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。 输入数据 (base.in) 输入文件的第一行包含两个整数N,K，含义如上所述。 第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。 第三行包含N个整数，表示C1,C2,…CN。 第四行包含N个整数，表示S1,S2,…,SN。 第五行包含N个整数，表示W1,W2,…,WN。 Input

输出文件中仅包含一个整数，表示最小的总费用。 Output

3 2 1 2 2 3 2 1 1 0 10 20 30 Sample Input

4 Sample Output

40%的数据中，N<=500； 100%的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。 HINT

Source

Day1

记f[i][j]f[i][j]表示在第ii个村庄修建第jj个基站且不考虑第i + 1i+1~nn个村庄所需的最小费用。 则转移方程为f[i][j] = Min(f[k][j - 1] + cst[k][i]) + c[i](j - 1 \le k < i)f[i][j]=Min(f[k][j−1]+cst[k][i])+c​​​i​​​。其中cst[k][i]cst[k][i]表示第ii~kk个村庄之间没有被基站i, ki,k覆盖的村庄所需的赔偿费用，计算费用的复杂度为O(n)O(n)，则总复杂度为O(n^2k)O(n​2​​k)。 这样显然是不能通过的，我们考虑如何优化： 首先我们发现之前的转移方程可以去掉一维jj，实际上只要在最外层枚举jj就可以了，也就是f[i] = Min(f[k] + cst[k][i]) + c[i](j - 1 \le k < i)f[i]=Min(f[k]+cst[k][i])+c​​​i​​​。 而主要的消耗在计算cst[k][i]cst[k][i]上，也就是有多少个村庄需要赔偿。 对于任意一个村庄ii，记它所能被覆盖的左右边界st[i], ed[i]st[i],ed[i]（最左端、最右端可以覆盖到ii的基站位置，可用二分查找处理），然后在用邻接表记录eded值为ii的村庄有哪些，在这些村庄之前建立基站就覆盖不到ii了。 这样当我们推导i + 1i+1时，若从村庄11~st[k] - 1(ed[k] = i)st[k]−1(ed[k]=i)转移过来则必定要赔偿村庄kk的费用，我们就可以考虑用线段树来维护f[k] + cst[k][i]f[k]+cst[k][i]的值，即在区间[1, st[k] - 1][1,st[k]−1]加上村庄kk的费用，而转移即在区间[1, i - 1][1,i−1]找f[k] + cst[k][i]f[k]+cst[k][i]的最小值，总复杂度为O(nlogn \times k)O(nlogn×k)。 写了两边，但我仍然不明白为什么答案一定出现在最后一个f[n] 我认为应该每一个地方都有可能是答案吧

#include#include#include#define N 22000#define inf 0x7f7f7f7fusing namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}vector g[N];int num,d[N],s[N],f[N],st[N],ed[N],w[N],n,k,c[N],root;struct node{ int l,r,left,right,min,lazy;}tree[N<<2];inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].min=min(tree[l].min,tree[r].min);}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r;tree[x].lazy=0; if (l==r) {tree[x].left=tree[x].right=0;tree[x].min=f[l];return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}inline void pushdown(int x){ if (!tree[x].lazy) return; int l=tree[x].left,r=tree[x].right; tree[l].lazy+=tree[x].lazy;tree[r].lazy+=tree[x].lazy; tree[l].min+=tree[x].lazy;tree[r].min+=tree[x].lazy; tree[x].lazy=0;}void insert1(int x,int l,int r,int v){ if (l>r) return; if (l<=tree[x].l&&r>=tree[x].r){tree[x].min+=v;tree[x].lazy+=v;return;} int mid=tree[x].l+tree[x].r>>1;pushdown(x); if (l<=mid) insert1(tree[x].left,l,r,v); if (r>mid) insert1(tree[x].right,l,r,v); update(x); }int query(int x,int l,int r){ if (l>r) return 0; if (l<=tree[x].l&&r>=tree[x].r) return tree[x].min; int mid=tree[x].l+tree[x].r>>1;pushdown(x);int tmp=inf; if(l<=mid) tmp=min(tmp,query(tree[x].left,l,r)); if (r>mid) tmp=min(tmp,query(tree[x].right,l,r)); return tmp;}int main(){ freopen("bzoj1835.in","r",stdin); n=read();k=read(); 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]=inf;w[n]=inf; for (int i=1;i<=n;++i){ st[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d; ed[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d; if (d[ed[i]]>d[i]+s[i]) --ed[i]; g[ed[i]].push_back(i); } int tmp=0,ans; for (int i=1;i<=n;++i){ f[i]=tmp+c[i]; for (int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。