博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P2605 基站选址
阅读量:6705 次
发布时间:2019-06-25

本文共 6702 字,大约阅读时间需要 22 分钟。

神TM毒瘤线段树优化DP......新姿势get。

题意:有n个村庄,在里面选不多于k个建立基站。

建立基站要ci的费用。如果一个村庄方圆si内没有基站,那么又要支出wi的费用。求最小费用。

解:很显然想到DP,f[i][j]表示前i个村庄里面放了j个基站,其中第i个一定选的最小费用。费用只统计不超过i的。

转移就是枚举从p转移,对于p到i的每一个,检查是否需要付钱。

这样是n³k的,只有20分。

1 #include 
2 #include
3 4 typedef long long LL; 5 const int N = 20010; 6 const LL INF = 0x3f3f3f3f3f3f3f3f; 7 8 LL d[N], s[N], f[N][210], c[N], w[N]; 9 int n, first[N], last[N];10 11 inline LL val(int l, int r) {12 LL ans = 0;13 for(int i = l + 1; i < r; i++) {14 if(l < first[i] && r > last[i]) {15 ans += w[i];16 }17 }18 return ans;19 }20 21 int main() {22 int k;23 LL ans = 0;24 scanf("%d%d", &n, &k);25 for(int i = 2; i <= n; i++) {26 scanf("%lld", &d[i]);27 }28 for(int i = 1; i <= n; i++) {29 scanf("%lld", &c[i]);30 }31 for(int i = 1; i <= n; i++) {32 scanf("%lld", &s[i]);33 }34 for(int i = 1; i <= n; i++) {35 scanf("%lld", &w[i]);36 ans += w[i];37 f[i][0] = f[i - 1][0] + w[i];38 }39 40 for(int i = 1; i <= n; i++) { // prework41 int l = 1, r = i;42 while(l < r) {43 int mid = (l + r) >> 1;44 if(d[mid] >= d[i] - s[i]) {45 r = mid;46 }47 else {48 l = mid + 1;49 }50 }51 first[i] = r;52 l = i;53 r = n;54 while(l < r) {55 int mid = (l + r + 1) >> 1;56 if(d[mid] <= d[i] + s[i]) {57 l = mid;58 }59 else {60 r = mid - 1;61 }62 }63 last[i] = r;64 }65 66 for(int j = 1; j <= k + 1; j++) {67 for(int i = 1; i <= n + 1; i++) {68 // f[i][j] = std::min(f[p][j - 1] + val69 if(j == 1) {70 f[i][j] = c[i] + val(0, i);71 }72 else {73 f[i][j] = INF;74 for(int p = j - 1; p < i; p++) {75 f[i][j] = std::min(f[i][j], f[p][j - 1] + val(p, i) + c[i]);76 }77 }78 }79 if(j > 1) {80 ans = std::min(ans, f[n + 1][j]);81 }82 }83 84 printf("%lld", ans);85 return 0;86 }
20分代码

然后我又想到了网络流,发现好像可以搞成最大权闭合子图来做,但是那个k的限制不好处理.....

最后光荣爆0了。

正解是线段树优化DP,但是怎么个优化法呢?

转移方程:f[i][j] = f[p][j - 1] + val(p, i) + c[i]

黑科技就是用线段树维护等式右边......下标就是p。

具体来说,我们当前正在考虑i。

那么f[i][j]就是min(0, i - 1),直接在线段树上查询即可。

线段树的初始值是f[p][j - 1],我们要动态的加上val(p, i)

每个点都有一个last,表示在i ~ last这段区间建基站的话能覆盖到它。

设last[v] = i,那么在i及之前的DP值都不会加上w[v],因为v之前的不会考虑到v,v ~ i的会覆盖到v。

i及之后的,有一部分转移要加上w[v],就是first[v]之前的部分。

因为first ~ i的转移会覆盖v,而i之后的转移会计算v。所以这些都不用计算v。

此时我们把0 ~ first[v] - 1的区间全部加上w[i]即可。

然后每次循环一个新j的时候把线段树初始化。

细节处理繁多......

1 #include 
2 #include
3 #include
4 5 typedef long long LL; 6 const int N = 20010; 7 const LL INF = 0x3f3f3f3f3f3f3f3f; 8 9 LL d[N], s[N], f[N][210], c[N], w[N]; 10 int n, first[N], last[N], Time; 11 std::vector
v[N]; 12 13 LL small[N << 2], tag[N << 2]; 14 15 inline void pushup(int o) { 16 small[o] = std::min(small[o << 1], small[o << 1 | 1]); 17 return; 18 } 19 20 inline void pushdown(int o) { 21 if(tag[o]) { 22 int ls = o << 1; 23 int rs = ls | 1; 24 tag[ls] += tag[o]; 25 tag[rs] += tag[o]; 26 small[ls] += tag[o]; 27 small[rs] += tag[o]; 28 tag[o] = 0; 29 } 30 return; 31 } 32 33 void add(int L, int R, LL v, int l, int r, int o) { 34 if(L <= l && r <= R) { 35 tag[o] += v; 36 small[o] += v; 37 return; 38 } 39 int mid = (l + r) >> 1; 40 pushdown(o); 41 if(L <= mid) { 42 add(L, R, v, l, mid, o << 1); 43 } 44 if(mid < R) { 45 add(L, R, v, mid + 1, r, o << 1 | 1); 46 } 47 pushup(o); 48 return; 49 } 50 51 LL ask(int L, int R, int l, int r, int o) { 52 if(L <= l && r <= R) { 53 return small[o]; 54 } 55 int mid = (l + r) >> 1; 56 pushdown(o); 57 LL ans = INF; 58 if(L <= mid) { 59 ans = std::min(ans, ask(L, R, l, mid, o << 1)); 60 } 61 if(mid < R) { 62 ans = std::min(ans, ask(L, R, mid + 1, r, o << 1 | 1)); 63 } 64 return ans; 65 } 66 67 void clear(int l, int r, int o) { 68 tag[o] = 0; 69 if(l == r) { 70 small[o] = f[r - 1][Time - 1]; 71 return; 72 } 73 int mid = (l + r) >> 1; 74 clear(l, mid, o << 1); 75 clear(mid + 1, r, o << 1 | 1); 76 pushup(o); 77 return; 78 } 79 80 int main() { 81 int k; 82 LL ans = 0; 83 scanf("%d%d", &n, &k); 84 for(int i = 2; i <= n; i++) { 85 scanf("%lld", &d[i]); 86 } 87 for(int i = 1; i <= n; i++) { 88 scanf("%lld", &c[i]); 89 } 90 for(int i = 1; i <= n; i++) { 91 scanf("%lld", &s[i]); 92 } 93 for(int i = 1; i <= n; i++) { 94 scanf("%lld", &w[i]); 95 ans += w[i]; 96 f[i][0] = f[i - 1][0] + w[i]; 97 } 98 99 for(int i = 1; i <= n; i++) { // prework100 int l = 1, r = i;101 while(l < r) {102 int mid = (l + r) >> 1;103 if(d[mid] >= d[i] - s[i]) {104 r = mid;105 }106 else {107 l = mid + 1;108 }109 }110 first[i] = r;111 l = i;112 r = n;113 while(l < r) {114 int mid = (l + r + 1) >> 1;115 if(d[mid] <= d[i] + s[i]) {116 l = mid;117 }118 else {119 r = mid - 1;120 }121 }122 last[i] = r;123 v[r].push_back(i);124 }125 126 for(int i = 1; i <= n + 1; i++) {127 f[i][0] = INF;128 }129 130 for(int j = 1; j <= k + 1; j++) {131 Time = j;132 clear(1, n + 1, 1);133 for(int i = 0; i <= n + 1; i++) {134 // ask f[i][j]135 if(i >= j) {136 f[i][j] = ask(1, i, 1, n + 1, 1) + c[i];137 }138 else {139 f[i][j] = INF;140 }141 // insert142 for(int p = 0; p < v[i].size(); p++) {143 add(1, first[v[i][p]], w[v[i][p]], 1, n + 1, 1);144 }145 }146 if(j > 1) {147 ans = std::min(ans, f[n + 1][j]);148 }149 }150 151 printf("%lld", ans);152 return 0;153 }
AC代码

思考:如果si表示能覆盖方圆si的村庄,又如何?

转移方程写出来,发现就是一个简单的前缀最大值优化。要处理一下前缀和为负的这种情况...

转载于:https://www.cnblogs.com/huyufeifei/p/10271080.html

你可能感兴趣的文章
深入浅出JavaScript运行机制
查看>>
LeetCode 272 Closest Binary Tree Traversal II 解题思路
查看>>
html中表单提交
查看>>
video自动播放 隐藏播放控制条,并且用点击 video 元素的时候 控制暂停和播放...
查看>>
【go密码学】-数字签名
查看>>
代码重构之消除分支结构
查看>>
ingress controller学习记录
查看>>
328. Odd Even Linked List
查看>>
redis学习笔记(三)--Redis的功能
查看>>
MySQL性能调优与架构设计(二)—— MySQL存储引擎简介
查看>>
NeurIPS 2018 中的贝叶斯研究
查看>>
Android 音视频入门之音频采集、编码、播放
查看>>
python并发模块之concurrent.futures(一)
查看>>
1月10日云栖精选夜读 | 12亿行代码,阿里巴巴这一年的技术报告和梦想报告 ...
查看>>
Spring4定时任务配置
查看>>
ApiPost自动化测试基础之:接口参数依赖的情景处理
查看>>
短视频程序的魅力,你为什么喜欢抖音?知乎大神的回答
查看>>
智能手机背后的利益链:赚了满钵的供应商,提心吊胆的新技术者
查看>>
C语言参考库
查看>>
Spring Boot 项目搭建
查看>>