三沣开发知识 购物 网址 游戏 小说 股票 美女 租车 短信 新闻 笑话 | 开发 汉字 下载 软件 图书馆 图片
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> P2605 [ZJOI2010]基站选址 -> 正文阅读
 

[C++]P2605 [ZJOI2010]基站选址

P2605 [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。
记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](j−1≤k<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](j−1≤k<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)。
但是不知道为什么怎么调都不对,。。。


  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<queue>
  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<<edge[j].v<<" "<<W[edge[j].v]<<endl;
129                     if(W[edge[j].v]==INF)continue;
130                     now+=W[edge[j].v];
131                 }
132                 
133             }
134             ans=dp[n];
135         }
136         else
137         {         
138             Build_Tree(1,1,n);int y;
139         //    for(int ii=1;ii<=10;ii++)
140         //        cout<<tree[ii].w<<" ";
141         //    cout<<endl;
142             for(int j=1;j<=n;j++)
143             {
144                 dp[j]= ((j>(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 <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 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 <class T> inline T Min(const T &a, const T &b) {return a < b? a : b;} 21 template <class T> 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 }

  C++ 最新文章
分享一些好的文章,致曾经苦苦思索的我
枚举类型 enum 用法
QT开发应用程序的欢迎界面
QT网络编程Tcp下C/S架构的即时通信
opencv3中SurfFeatureDetector、SurfDescri
int *p[3]和int (*p)[3]区别
跨平台大纲
杭电1518
面试基础(二)
多维数组和指针探讨
上一篇文章      下一篇文章      查看所有文章
加:2017-08-12 23:24:17  更:2017-08-12 23:24:21 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 Android开发 站长 古典小说 网文精选 搜图网 美图 中国文化英文版 多播 租车 短信 看图
2017-8-21 14:18:16
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库