【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
", ans);
return 0;
}