「BZOJ1835」[ZJOI2010]基站选址

Description

NN个村庄坐落在一条直线上,第i(i>1)i(i>1)个村庄距离第1个村庄的距离为DiD_i
需要在这些村庄中建立不超过KK个通讯基站,在第ii个村庄建立基站的费用为CiC_i。如果在距离第ii个村庄不超过SiS_i的范围内建立了一个通讯基站,那么就成它被覆盖了。如果第ii个村庄没有被覆盖,则需要向他们补偿,费用为WiW_i

现在的问题是,选择基站的位置,使得总费用最小。

Input

输入文件的第一行包含两个整数N,KN,K,含义如上所述。

第二行包含N1N-1个整数,分别表示D2,D3,,DND_2,D_3,\cdots,D_N ,这N1N-1个数是递增的。

第三行包含NN个整数,表示C1,C2,CNC_1,C_2,\cdots C_N

第四行包含NN个整数,表示S1,S2,,SNS_1,S_2,\cdots ,S_N

第五行包含NN个整数,表示W1,W2,,WNW_1,W_2,\cdots ,W_N

Output

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

Sample Input

1
2
3
4
5
3 2
1 2
2 3 2
1 1 0
10 20 30

Sample Output

1
4

HINT

40%40\%的数据中,N500N\leq500
100%100\%的数据中,KN,K100,N20,000,Di1000000000,Ci10000,Si1000000000,Wi10000K\leq N,K\leq 100,N\leq20,000,D_i\leq1000000000,C_i\leq10000,S_i\leq1000000000,W_i\leq10000

Solution

force

fi,jf_{i,j}表示第ii个村庄为止,装了jj的基站,且在ii装了基站,所需最小花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 21000;
struct T {
ll d, c, s, w;
}a[N];
bool cmp(T _x, T _y) {
return _x.d < _y.d;
}
int n, m;
ll f[510][510], g[510][510], t[510][510];
int main() {
freopen("1835.in","r",stdin);
freopen("1835.out","w",stdout);
n = read(); m = read();
for(int i = 2; i <= n; ++i)
a[i].d = read();
for(int i = 1; i <= n; ++i)
a[i].c = read();
for(int i = 1; i<= n; ++i)
a[i].s = read();
for(int i = 1; i <= n; ++i)
a[i].w = read();
sort(a +1, a + 1 + n, cmp);

memset(f, 0x3f, sizeof f);
a[0].d = -1e16;
a[n + 1].d = 1e16;
f[0][0] = 0;
for(int i = 0; i <= n; ++i) {
for(int j = i; j <= n+1; ++j) {
for(int k = i; k < j; ++k) {
if(k > i && a[k].d - a[k].s > a[i].d && a[k].d + a[k].s < a[j].d )
g[i][j] += a[k].w;
if(a[k].d + a[k].s < a[j].d)
t[i][j] += a[k].w;
}
}
}
for(int i = 1; i <= n; ++i) {
f[i][0] = a[i].w + f[i - 1][0];
for(int j = 1; j <= m && j <= i; ++j) {
for(int k = 0; k < i; ++k) {
if(j > 1)
f[i][j] = min(f[i][j], f[k][j - 1] + g[k][i] + a[i].c);
else f[i][j] = min(f[i][j], f[k][0] + t[k][i] + a[i].c);
}
}
}
ll ans = 1e18;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m && j <= i; ++j)
ans = min(ans, f[i][j] + g[i][n + 1]);
ans = min(ans, f[n][0]);
writeln(ans);
return 0;
}

优化

可以最外层枚举jj,循环kk次,然后fi=min{fk+gk,i}+cif_i=\min\{f_k+g_{k,i}\}+c_i表示第kk次在ii号庄家装基塔的最小代价。
计算的瓶颈在gk,ig_{k,i}上面。
考虑(i1)i(i-1)\to i的时候,gk,i1g_{k,i-1}的变化。

  1. gk,i=gk,i1g_{k,i}=g_{k,i-1}
  2. gk,i=gk,i1+g_{k,i}=g_{k,i-1}+原本能覆盖,现在不能被覆盖的
    每个村庄记录基塔的有效范围,LiL_iRiR_i表示在[Li,Ri][L_i,R_i]之内建造是不用赔偿的,并在vector下表为RiR_i的地方push。 每次遍历i1i-1的vector把其对应元素的[1,Lk1][1,L_k-1]区间ff值内都加上wkw_k。表示如果从[1,Lk1][1,L_k-1]转移的话现在开始都需要支付wkw_k,否则可以被[Lk,i1][L_k,i-1]庄家的基塔给覆盖了。
    可以开一个点n+1n+1,每次和fn+1f_{n+1}取最小值就得到答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 21000;
struct T {
ll d, c, s, w;
}a[N];
bool cmp(T _x, T _y) {
return _x.d < _y.d;
}
int n, m;
ll f[N];
int ls[N*4],rs[N*4];
ll t[N*4], tag[N*4];
int L[N], R[N];
#define lch (o<<1)
#define rch (o<<1|1)
void build(int o, int l, int r) {
ls[o] = l, rs[o] = r; tag[o] = 0;
if(l == r) {
t[o] = f[l];
return;
}
int mid = (l + r) >> 1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
t[o] = min(t[lch], t[rch]);
}
void down(int o) {
if(tag[o]) {
tag[lch] += tag[o];
tag[rch] += tag[o];
t[lch] += tag[o];
t[rch] += tag[o];
tag[o] = 0;
}
}
ll query(int o, int l, int r) {
if(ls[o] >= l && rs[o] <= r) return t[o];
int mid = (ls[o] + rs[o]) >> 1;
down(o);
if(r <= mid) return query(lch, l, r);
if(l > mid) return query(rch, l, r);
return min(query(lch, l, r), query(rch, l, r));
}
void add(int o, int l, int r, ll v) {
if(ls[o] >= l &&rs[o] <= r) {
t[o] += v;
tag[o] += v;
return;
}
down(o);
int mid = (ls[o] + rs[o]) >> 1;
if(l <= mid) add(lch, l, r, v);
if(r > mid) add(rch, l, r, v);
t[o] = min(t[lch], t[rch]);
}
int findl(int x) {
int l = 0, r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
//printf("l=%d,r=%d,mid=%d %d %d\n", l, r, mid, a[mid].d,x);
if(a[mid].d >= x) r = mid;
else l = mid;
}
return r;
}
int findr(int x) {
int l = 1, r = n + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(a[mid].d <= x) l = mid;
else r = mid;
}
return l;
}
vector<int>v[N];
int main() {
n = read(); m = read();
for(int i = 2; i <= n; ++i)
a[i].d = read();
for(int i = 1; i <= n; ++i)
a[i].c = read();
for(int i = 1; i<= n; ++i)
a[i].s = read();
for(int i = 1; i <= n; ++i)
a[i].w = read();
sort(a +1, a + 1 + n, cmp);
a[0].d = -1e18;
a[n + 1].d = 1e18;
for(int i = 1; i <= n; ++i) {
L[i] = findl(a[i].d - a[i].s);
R[i] = findr(a[i].d + a[i].s);
v[R[i]].pb(i);
}
ll ans = 1e18;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int T = 0; T <= m; ++T) {
build(1, 0, n);
if(T == 0) {
for(int i = 1; i <= n + 1; ++i) {
for(int j = 0; j < v[i - 1].size(); ++j)
add(1, 0, i - 1, a[v[i - 1][j]].w);
f[i] = query(1, 0, i - 1) + a[i].c;
}
} else {
for(int i = 1; i <= n + 1; ++i) {
for(int j = 0; j < v[i - 1].size(); ++j)
add(1, 0, L[v[i - 1][j]] - 1, a[v[i - 1][j]].w);
f[i] = query(1, 0, i - 1) + a[i].c;
}
}
ans = min(ans, f[n + 1]);
}
writeln(ans);
return 0;
}