P2605 [ZJOI2010]基站选址-白红宇

P2605 [ZJOI2010]基站选址

阅读量：5902 次

发布时间：2019-06-19

本文共 8147 字，大约阅读时间需要 27 分钟。

题目描述

有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 21 22 3 21 1 010 20 30

输出样例#1：

说明

40%的数据中，N<=500；

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

则转移方程为 $\le k < i)f[i][j]=Min(f[k][j−1]+cst[k][i])+c[i](j−1≤k<i)。其中cst[k][i]cst[k][i]表示第ii~kk个村庄之间没有被基站i, ki,k覆盖的村庄所需的赔偿费用，计算费用的复杂度为O(n)O(n)，则总复杂度为O(n^2k)O(n2k)。$

这样显然是不能通过的，我们考虑如何优化：

首先我们发现之前的转移方程可以去掉一维 $\le k < i)f[i]=Min(f[k]+cst[k][i])+c[i](j−1≤k<i)。$

而主要的消耗在计算

对于任意一个村庄

这样当我们推导 $\times k)O(nlogn×k)。$

但是不知道为什么怎么调都不对，。。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define INF 0x7ffff 9 #define ls k<<1 10 #define rs k<<1|1 11 using namespace std; 12 const int MAXN=4e4+5; 13 inline void read(int &n) 14 { 15 char c='+';bool flag=0;n=0; 16 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 17 while(c>='0'&&c<='9')n=n*10+c-48,c=getchar(); 18 } 19 struct node 20 { 21 int u,v,nxt; 22 }edge[MAXN]; 23 int head[MAXN]; 24 int num=1; 25 inline void add_edge(int x,int y) 26 { 27 edge[num].u=x; 28 edge[num].v=y; 29 edge[num].nxt=head[x]; 30 head[x]=num++; 31 } 32 struct T 33 { 34 int l,r,w,tag; 35 }tree[MAXN]; 36 int n,k; 37 int D[MAXN]; 38 int C[MAXN]; 39 int S[MAXN]; 40 int W[MAXN]; 41 int st[MAXN]; 42 int ed[MAXN]; 43 int dp[MAXN];// 修建了i个基站的费用 44 int ans; 45 inline void update(int k) 46 { 47 tree[k].w=min(tree[ls].w,tree[rs].w); 48 } 49 inline void pushdown(int k) 50 { 51 if(!tree[k].tag) return ; 52 tree[ls].w+=tree[k].tag; 53 tree[ls].tag+=tree[k].tag; 54 tree[rs].w+=tree[k].tag; 55 tree[rs].w+=tree[k].tag; 56 tree[k].tag=0; 57 } 58 inline void Build_Tree(int k,int ll,int rr) 59 { 60 tree[k].tag=0; 61 tree[k].l=ll;tree[k].r=rr; 62 if(ll==rr) 63 { 64 tree[k].w=dp[ll]; 65 return ; 66 } 67 int mid=(ll+rr)>>1; 68 Build_Tree(ls,ll,mid);Build_Tree(rs,mid+1,rr); 69 update(k); 70 } 71 inline int query(int k,int ql,int qr) 72 { 73 if(tree[k].l==ql&&tree[k].r==qr) 74 return tree[k].w; 75 pushdown(k); 76 int mid=(tree[k].l+tree[k].r)>>1; 77 if(qr<=mid) return query(ls,ql,qr); 78 else if(ql>mid) return query(rs,ql,qr); 79 else return min(query(ls,ql,mid), 80 query(rs,mid+1,qr)); 81 } 82 inline void change(int k,int ql,int qr,int val) 83 { 84 if(tree[k].l==ql&&tree[k].r==qr) 85 { 86 tree[k].w+=val,tree[k].tag+=val;return ; 87 } 88 pushdown(k); 89 int mid=(tree[k].l+tree[k].r)>>1; 90 if(qr<=mid) change(ls,ql,qr,val); 91 else if(ql>mid) change(rs,ql,qr,val); 92 else 93 { 94 change(ls,ql,mid,val); 95 change(rs,mid+1,qr,val); 96 } 97 update(k); 98 } 99 int main()100 {101 freopen("base.in","r",stdin);102 freopen("base.out","w",stdout);103 read(n);read(k);k++;104 memset(head,-1,sizeof(head));105 for(int i=2;i<=n;i++) read(D[i]);106 for(int i=1;i<=n;i++) read(C[i]);107 for(int i=1;i<=n;i++) read(S[i]);108 for(int i=1;i<=n;i++) read(W[i]);109 ++n;D[n]=W[n]=INF;110 for(int i=1;i<=n;i++)111 {112 st[i]=lower_bound(D+1,D+n+1,D[i]-S[i])-D;113 ed[i]=lower_bound(D+1,D+n+1,D[i]+S[i])-D;114 if(D[ed[i]]>S[i]+D[i]) ed[i]--;115 add_edge(ed[i],i);116 }117 118 for(int i=1;i<=k;i++)119 {120 if(i==1)121 {122 int now=0;123 for(int k=1;k<=n;k++)124 {125 dp[k]=now+C[k];126 for(int j=head[k];j!=-1;j=edge[j].nxt)127 {128 //cout<
             
              <<" "<
              
               <
               
                (i-1)) ? query(1,i-1,j-1) : 0 )+ C[j];145 for(int k=head[j];k!=-1;k=edge[k].nxt)146 if(st[y=edge[k].v]>1)147 change(1,1,st[y]-1,W[y]);148 }149 ans=min(ans,dp[n]);150 }151 }152 printf("%d",ans);153 return 0;154 }

UKE

本代码来自：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2605   1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #define sL (s << 1)  6 #define sR (s << 1 | 1)  7   8 using namespace std;  9 const int Maxn = 0x3f3f3f3f; 10 const int N = 2e4 + 5, M = N << 2; 11 int d[N], c[N], w[N], s[N], st[N], ed[N], f[N];  12 int n, k, Ans, val[M], tag[M]; 13  14 struct point 15 { 16     int to; point *nxt; 17 }a[M], *T = a, *lst[N];  18  19 inline void addEdge(const int &x, const int &y) {T->nxt = lst[x]; T->to = y; lst[x] = T++;}  20 template 
         
           inline T Min(const T &a, const T &b) {
   return a < b? a : b;} 21 template 
          
            inline void CkMin(T &a, const T &b) { if (a > b) a = b;} 22 23 inline int get() 24 { 25 char ch; bool f = false; int res = 0; 26 while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); 27 if (ch == '-') f = true; 28 else res = ch - '0'; 29 while ((ch = getchar()) >='0' && ch <= '9') 30 res = (res << 3) + (res << 1) + ch - '0'; 31 return f? ~res + 1 : res; 32 } 33 34 inline void put(int x) 35 { 36 if (x < 0) 37 x = ~x + 1, putchar('-'); 38 if (x > 9) put(x / 10); 39 putchar(x % 10 + 48); 40 } 41 42 inline void Push(const int &s) {val[s] = Min(val[sL], val[sR]);} 43 inline void Add(const int &s, const int &z) 44 {val[s] += z; tag[s] += z;} 45 46 inline void Down(const int &s) 47 { 48 if (!tag[s]) return ; 49 Add(sL, tag[s]); Add(sR, tag[s]); tag[s] = 0; 50 } 51 52 inline void Build(const int &s, const int &l, const int &r) 53 { 54 tag[s] = 0; 55 if (l == r) return (void)(val[s] = f[l]); 56 int mid = l + r >> 1; 57 Build(sL, l, mid); Build(sR, mid + 1, r); 58 Push(s); 59 } 60 61 inline int Query(const int &s, const int &l, const int &r, const int &x, const int &y) 62 { 63 if (l == x && r == y) return val[s]; 64 Down(s); int mid = l + r >> 1; 65 if (y <= mid) return Query(sL, l, mid, x, y); 66 else if (x > mid) return Query(sR, mid + 1, r, x, y); 67 else return Min(Query(sL, l, mid, x, mid), 68 Query(sR, mid + 1, r, mid + 1, y)); 69 } 70 71 inline void Modify(const int &s, const int &l, const int &r, const int &x, const int &y, const int &z) 72 { 73 if (l == x && r == y) return Add(s, z); 74 Down(s); int mid = l + r >> 1; 75 if (y <= mid) Modify(sL, l, mid, x, y, z); 76 else if (x > mid) Modify(sR, mid + 1, r, x, y, z); 77 else 78 { 79 Modify(sL, l, mid, x, mid, z); 80 Modify(sR, mid + 1, r, mid + 1, y, z); 81 } 82 Push(s); 83 } 84 85 int main() 86 { 87 n = get(); k = get() + 1; 88 for (int i = 2; i <= n; ++i) d[i] = get(); 89 for (int i = 1; i <= n; ++i) c[i] = get(); 90 for (int i = 1; i <= n; ++i) s[i] = get(); 91 for (int i = 1; i <= n; ++i) w[i] = get(); 92 ++n; d[n] = w[n] = Maxn; 93 //当我们推导i时，我们只考虑了它和前面的基站产生的影响 94 //这时对于最后一个基站我们不会考虑它和之后的村庄产生的影响 95 //则我们可以在最后增加一个村庄 96 //保证它必定被作为基站（无建设费用）且不对前面产生影响 97 //这样就不会有遗漏的了 98 for (int i = 1; i <= n; ++i) 99 {100 st[i] = lower_bound(d + 1, d + n + 1, d[i] - s[i]) - d;101 ed[i] = lower_bound(d + 1, d + n + 1, d[i] + s[i]) - d;102 if (d[ed[i]] > d[i] + s[i]) ed[i]--; addEdge(ed[i], i);103 //lower_bound查找的是大于等于x的第一个数104 //而ed[i]要求的是小于等于x的最后一个数105 //所以判断一下减一就可以了 106 }107 for (int i = 1; i <= k; ++i)108 if (i == 1)109 {110 int res = 0;111 for (int j = 1; j <= n; ++j)112 {113 f[j] = res + c[j];114 for (point *e = lst[j]; e; e = e->nxt)115 res += w[e->to];116 }117 Ans = f[n];118 }119 else 120 {121 Build(1, 1, n); int y;122 for (int j = 1; j <= n; ++j)123 {124 //注意线段树区间的边界条件125 f[j] = (j > i - 1 ? Query(1, 1, n, i - 1, j - 1) : 0) + c[j];126 for (point *e = lst[j]; e; e = e->nxt)127 if (st[y = e->to] > 1) Modify(1, 1, n, 1, st[y] - 1, w[y]);128 //这里其实只要修改区间[i, st[y] - 1]就行了129 //不过询问/修改的区间长对于线段树其实更快 130 }131 CkMin(Ans, f[n]);132 }133 return put(Ans), 0;134 }

转载地址：http://plkpx.baihongyu.com/

你可能感兴趣的文章