【LG2605】[ZJOI2010]基站选址

题面

洛谷

题解

先考虑一下暴力怎么写，设\(f_{i,j}\)表示当前\(dp\)到\(i\)，且强制选\(i\)，目前共放置\(j\)个的方案数。

那么转移为\(f_{i,j}=\min_{k=1}^{i-1} \{f_{k,j-1}+cost_{k,i}\}+c_i\)，其中\(cost_{l,r}\)表示\([l,r]\)只选两端中间的补偿。

其中\(cost\)只需要\(O(\frac {n^3}4)\)预处理就好了，那么复杂度为\(O(\frac {n^3}4+kn^2)\)。

考虑优化这个暴力，此时我们只需要对于\(f_{i,j}\)找到满足条件的最小的\(k\)即可。

而对于一个位置\(i\)，它要贡献\(w_i\)当且仅当一段区间内没有建基站，这个可以二分出来。

我们对这些按右端点区间排个序，那么可以知道过了某个位置\(i\)，对于右端点在\(i\)的所有区间的左端点\(l\)，区间\([1,l-1]\)内的\(f\)转移的花费必然会增加，那么用线段树维护区间取\(\min\)及区间加法即可。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();

    if (ch == '-') w = -1 , ch = getchar();

    while (ch >= '0' && ch <= '9') data = (data << 1) + (data << 3) + (ch ^ 48), ch = getchar();

    return w * data;

}

#define MAX_N 20005

int N, K;

int D[MAX_N], C[MAX_N], S[MAX_N], W[MAX_N];

int dp[MAX_N];

struct Line {

	int l, r;

	bool operator < (const Line & rhs) const {

		return r < rhs.r;

	}

} p[MAX_N];

vector<int> vec[MAX_N];

#define lson (o << 1)

#define rson (o << 1 | 1)

int addv[MAX_N << 2], minv[MAX_N << 2];

void pushup(int o) { minv[o] = min(minv[lson], minv[rson]); }

void puttag(int o, int w) { minv[o] += w, addv[o] += w; }

void pushdown(int o) {

	puttag(lson, addv[o]);

	puttag(rson, addv[o]);

	addv[o] = 0;

}

void build(int o, int l, int r) {

	addv[o] = 0;

	if (l == r) {

		minv[o] = dp[l];

		return ;

	}

	int mid = (l + r) >> 1;

	build(lson, l, mid);

	build(rson, mid + 1, r);

	pushup(o);

}

void modify(int o, int l, int r, int ql, int qr, int w) {

	if (ql > qr) return ;

	if (ql <= l && r <= qr) {

		puttag(o, w);

		return ;

	}

	pushdown(o);

	int mid = (l + r) >> 1;

	if (ql <= mid) modify(lson, l, mid, ql, qr, w);

	if (qr > mid) modify(rson, mid + 1, r, ql, qr, w);

	pushup(o);

}

int query(int o, int l, int r, int ql, int qr) {

	if (ql > qr) return 0;

	if (ql <= l && r <= qr) return minv[o];

	pushdown(o);

	int mid = (l + r) >> 1, res = INT_MAX;

	if (ql <= mid) res = min(res, query(lson, l, mid, ql, qr));

	if (qr > mid) res = min(res, query(rson, mid + 1, r, ql, qr));

	return res;

}

int main () {

	N = gi(), K = gi();

	for (int i = 2; i <= N; i++) D[i] = gi();

	for (int i = 1; i <= N; i++) C[i] = gi();

	for (int i = 1; i <= N; i++) S[i] = gi();

	for (int i = 1; i <= N; i++) W[i] = gi();

	for (int i = 1, l, r, pos = 1; i <= N; i++) {

		l = 1, r = i - 1, pos = i;

		while (l <= r) {

			int mid = (l + r) >> 1;

			if (D[i] - D[mid] <= S[i]) pos = mid, r = mid - 1;

			else l = mid + 1;

		}

		p[i].l = pos;

		l = i + 1, r = N, pos = i;

		while (l <= r) {

			int mid = (l + r) >> 1;

			if (D[mid] - D[i] <= S[i]) pos = mid, l = mid + 1;

			else r = mid - 1;

		}

		p[i].r = pos;

	}

	for (int i = 1; i <= N; i++) vec[p[i].r].push_back(i);

	for (int i = 1, tmp = 0; i <= N + 1; i++) {

		dp[i] = tmp + C[i];

		for (int j = 0; j < vec[i].size(); j++)

			tmp += W[vec[i][j]];

	}

	int ans = dp[N + 1];

	for (int i = 1; i <= K; i++) {

		build(1, 1, N + 1);

		for (int j = 1; j <= N + 1; j++) {

			dp[j] = query(1, 1, N + 1, 1, j - 1) + C[j];

			for (int k = 0; k < vec[j].size(); ++k) {

				modify(1, 1, N + 1, 1, p[vec[j][k]].l - 1, W[vec[j][k]]);

			}

		}

		ans = min(ans, dp[N + 1]);

	}

	printf("%d\n", ans);

	return 0;

}