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

基站选址

题目链接： /

题目大意

一条直线上要在点上建一些基站，数量不能超过一个数，一个地方 i 会被基站覆盖仅当不超过 S[i] 的范围内有基站。

然后在一个地方建基站有一个花费，一个地方没有被基站覆盖也有一个补偿费用。 给出直线上点之间的位置距离，问你最小花费。

思路

这道题首先我们可以想想最垃圾的 dp 怎么打。

考虑 $f_{i,j}$ 为前 $i$ 个点中最后选的是 $i$ 号点，一共选了 $j$ 个点的最小花费。（而且是只考虑 $1\sim i$ 的花费，不管 $i+1\sim n$ 的赔偿费用）

那可以搞出转移方程： f i , j = min ⁡ { f k , j − 1 + p a y k , i } + c i ( j − 1 ≤ k < i ) 。 f_{i,j}=\min\{f_{k,j-1}+pay_{k,i}\}+c_i(j-1\leq k<i)。 fi,j​=min{

fk,j−1​+payk,i​}+ci​(j−1≤k<i)。

我们看到每次第二位只是调用前面的一个，那我们可以把第二位去掉。

那空间就可以了，但是时间还是 $O(n^{2}k)$，还是会超时（因为你要 $O(n)$ 算 $pa{y}_{k,i}$）。

那我们考虑优化这个地方。

首先，对于一个点，你可以求出要使它被覆盖，哪个区间内必须至少建一个基站。这个可以用二分快速解决。然后每个点都要求，那就是 $O(nlogn)$。 假设已经求了出来，左边界是 $g{l}_i$，右边界是 $g{r}_i$。

那我们考虑枚举 $i$ 的时候，怎么转。

分两种情况。 首先是选，这个是要统计到 $f_i$ 里面的。那上一个基站就在 $1\sim i-1$ 之间，那我们就在这些地方选最小值。 当然你不能直接枚举看，我们考虑用一个数据结构来优化。由于数是不停变化的，那我们考虑用线段树。 接着是不选，这个是留在给后面用的，那你就要考虑赔偿，那你要看哪些点要开始赔偿。

那如果这个不选了，临界的点就会碰不到了。那如果有一个点 $x$，它的 $g{r}_x$ 就是 $i$，那如果不选了 $i$，选 $i+1$ 或者更加以后的，就都覆盖不到这个点了，这个点也就要赔偿了。

那你只要用邻接表记录右边界为它的点，然后在从 $1$ 到左边界的左边加上赔偿费用即可。

为什么是左边界的左边？ 因为是左边界的左边，才会两边都没有基站，才要赔偿。（就是你建在左边界的左边，新的又不建，就要赔偿） 这个就是区间加值，也可以用线段树来做。

但是有一个问题，你每次只会解决它和它前面的，它后面的你还没看。

那你就在最后的点后面多开一个点，只会覆盖到它自己，而且没有费用，也不会被任何点覆盖。 那我们跑这个点的时候，就会把所有的边再看一次，就可以了。

代码

#include
   
    #include
    
     #define ll long long#define INF 0x3f3f3f3f3f3f3f3fusing namespace std;struct node {   	int to, nxt;}e[40010];struct Tree {   	ll x, lazy;}tree[160010];int n, k, c[20010], w[20010];int gl[20010], gr[20010];int le[20010], KK;ll d[20010], s[20010], f[20010], ans;void add(int x, int y) {   	e[++KK] = (node){   y, le[x]}; le[x] = KK; }void ef(int now) {   	int l = 0, r = now - 1;	while (l < r) {   		int mid = (l + r + 1) >> 1;		if (d[now] - d[now - mid] <= s[now]) l = mid;			else r = mid - 1;	}	gl[now] = now - l;//左边界		l = 0, r = n - now;	while (l < r) {   		int mid = (l + r + 1) >> 1;		if (d[now + mid] - d[now] <= s[now]) l = mid;			else r = mid - 1;	}	gr[now] = now + l;//右边界		add(gr[now], now);//记录那些点的右边界是这个点}void gotfirst() {   	ll now = 0;	for (int i = 1; i <= n; i++) {   		f[i] = now + c[i];//在这里建		for (int j = le[i]; j; j = e[j].nxt)			now += w[e[j].to];//如果不在这里建，有那些点要开始赔偿	}}void up(int now) {   //线段树操作	tree[now].x = min(tree[now << 1].x, tree[now << 1 | 1].x);}void down(int now) {   	tree[now << 1].x += tree[now].lazy;	tree[now << 1 | 1].x += tree[now].lazy;	tree[now << 1].lazy += tree[now].lazy;	tree[now << 1 | 1].lazy += tree[now].lazy;	tree[now].lazy = 0; }void build(int now, int l, int r) {   	tree[now].lazy = 0;	if (l == r) {   		tree[now].x = f[l];		return ;	}	int mid = l + ((r - l) >> 1);	build(now << 1, l, mid);	build(now << 1 | 1, mid + 1, r);	up(now);}ll get_ans(int now, int l, int r, int L, int R) {   //得到费用最小的那个	 if (L > R) return INF;	 if (l >= L && r <= R) return tree[now].x;	 	 down(now);	 int mid = l + ((r - l) >> 1);	 ll re = INF;	 if (L <= mid) re = min(re, get_ans(now << 1, l, mid, L, R));	 if (R >= mid + 1) re = min(re, get_ans(now << 1 | 1, mid + 1, r, L, R));	 	 return re;}void add_num(int now, int l, int r, int L, int R, ll addnum) {   	if (L > R) return ;	if (L <= l && R >= r) {   		tree[now].x += addnum;		tree[now].lazy += addnum;		return ; 	}		down(now);		int mid = l + ((r - l) >> 1);	if (L <= mid) add_num(now << 1, l, mid, L, R, addnum);	if (R >= mid + 1) add_num(now << 1 | 1, mid + 1, r, L, R, addnum);		up(now);		return ;}void work() {   	gotfirst();//预处理出一开始的情况	ans = f[n];		for (int i = 2; i <= k; i++) {   		build(1, 1, n);//记录原来的位置				for (int j = 1; j <= n; j++) {   			f[j] = c[j] + get_ans(1, 1, n, 1, j - 1);//选			for (int I = le[j]; I; I = e[I].nxt)//不选				add_num(1, 1, n, 1, gl[e[I].to] - 1, w[e[I].to]);		}				ans = min(ans, f[n]);	}}int main() {   	scanf("%d %d", &n, &k);	for (int i = 2; i <= n; i++) scanf("%lld", &d[i]);	for (int i = 1; i <= n; i++) scanf("%d", &c[i]);	for (int i = 1; i <= n; i++) scanf("%lld", &s[i]);	for (int i = 1; i <= n; i++) scanf("%d", &w[i]);		n++;	k++;	d[n] = INF;	w[n] = INF;	//这里在最后多加一个点，在这里建覆盖不到其他点，而且不会被任何点覆盖，建基站也没有费用	//这样其实就可以考虑到前面每个正常的基站对后面的影响	//因为你每次考虑只会考虑这个基站对它和前面的影响，以及前面的基站对它和它前面的影响	//那你最后一个基站的后面就不会被考虑，就需要再多弄一个点，使得没有遗漏		for (int i = 1; i <= n; i++) {   		ef(i);	}//二分出能覆盖到它的位置的左右边界		work();//线段树优化dp		printf("%lld", ans);		return 0;}