ZJOI2010 基站选址

未分类

$kn^2$ 的 DP 很简单，设 $f(i,j)$ 为第 $j$ 个村庄建造第 $i$ 个基站，只考虑前 $j$ 个村庄的花费。$f(i,j)=\min\limits_{i-1\leq k < j} \{f(i-1,k)+w(k,j)\}+c_j$ 其中 $w(k,j)$ 表示 $k$ 与 $j$ 中间的村庄需要赔偿的总额。考虑在 $j$ 逐渐变大的时候，如果有一个村庄的可被覆盖范围 $[l,r]$ 满足 $r=j$，以后的所有 $w(i<l,j)$ 都会加一。这个是一个区间加的形式，可以用线段树来维护每个 $f(i,j)+w(j,l)$，$l$ 就是每次不断增大的状态中的第二个变量。每个区间只会被用作加法一次（在一个阶段内），所以总复杂度为 $\mathcal O(nk\times \log_2 n)$。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int MAXN = 2e4;
const int MAXK = 1e2;
int n, K, ans;
int c[MAXN | 1], dp[MAXK | 1][MAXN | 1], sum[MAXN | 1];
LL d[MAXN | 1];
struct Range {
  int l, r; 
  LL w;
  Range() : l(0), r(0), w(0) {}
  friend bool operator< (const Range &lhs, const Range &rhs) {
    return lhs.r < rhs.r;
  }
} range[MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
void find(int x) {
  int l, r, mid;
  l = 1;
  r = x;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (d[x] - d[mid] <= range[x].w) {
      r = mid - 1;
      range[x].l = mid;
    } else l = mid + 1;
  }
  l = x;
  r = n;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (d[mid] - d[x] <= range[x].w) {
      l = mid + 1;
      range[x].r = mid;
    } else r = mid - 1;
  }
}
struct Node {
  int minv, lazy;
  Node *ch[2];
  Node() : minv(0), lazy(0) {
    ch[0] = ch[1] = NULL;
  }
} *root;
void pushUp(Node *o) {
  o -> minv = std::min(o -> ch[0] -> minv, o -> ch[1] -> minv);
}
void pushDown(Node *o) {
  if (o -> lazy != 0) {
    o -> ch[0] -> minv += o -> lazy;
    o -> ch[1] -> minv += o -> lazy;
    o -> ch[0] -> lazy += o -> lazy;
    o -> ch[1] -> lazy += o -> lazy;
    o -> lazy = 0;
  }
}
void build(Node *&o, int l, int r, int id) {
  if (o == NULL) o = new Node;
  else o -> lazy = 0;
  if (l == r) {
    o -> minv = dp[id][l];
    o -> lazy = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(o -> ch[0], l, mid, id);
  build(o -> ch[1], mid + 1, r, id);
  pushUp(o);
}
void modify(Node *o, int l, int r, int ql, int qr, int v) {
  if (ql <= l && r <= qr) {
    o -> minv += v;
    o -> lazy += v;
    return;
  }
  int mid = (l + r) >> 1;
  pushDown(o);
  if (ql <= mid) modify(o -> ch[0], l, mid, ql, qr, v);
  if (mid < qr) modify(o -> ch[1], mid + 1, r, ql, qr, v);
  pushUp(o);
}
int query(Node *o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return o -> minv;
  int mid = (l + r) >> 1, res = 1e9;
  pushDown(o);
  if (ql <= mid) res = query(o -> ch[0], l, mid, ql, qr);
  if (mid < qr) res = std::min(res, query(o -> ch[1], mid + 1, r, ql, qr));
  return res;
}
int main() {
  n = read();
  K = read();
  build(root, 1, n, 0);
  for (int i = 2; i <= n; ++i) scanf("%lld", d + i);
  for (int i = 1; i <= n; ++i) c[i] = read();
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &range[i].w);
    find(i);
  }
  for (int i = 1; i <= n; ++i) range[i].w = read();
  d[++n] = 1e9;
  ans = 1e9;
  int pot = 1;
  ++K;
  for (int i = 1; i <= n; ++i) {
    dp[1][i] = c[i];
    for (int j = 1; j < i; ++j) if (range[j].l > i || range[j].r < i) dp[1][i] += range[j].w;
  }
  ans = dp[1][n];
  std::sort(range + 1, range + 1 + n);
  for (int i = 2; i <= K; ++i) {
    build(root, 1, n, i - 1);
    memset(sum, 0, sizeof(sum));
    pot = 1;
    for (int j = i; j <= n; ++j) {
      while (pot <= n && range[pot].r < j) {
        if (i <= range[pot].l) modify(root, 1, n, i - 1, range[pot].l - 1, range[pot].w);
        ++pot;
      } 
      dp[i][j] = query(root, 1, n, i - 1, j - 1) + c[j];
    }
    ans = std::min(ans, dp[i][n]);
  }
  printf("%d\n", ans);
  return 0;
}