HAOI2011 problem a

未分类

对于一组 $(a_i, b_i)$ 可以看成表示与第 $i$ 个人同分的人的区间是 $[a_i+1,n-b_i]$。那么将一定假的情况先剔除，接下来可以将问题看成是选择若干个不相交的区间，使得区间的权值和最大。使用树状数组优化 DP 即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int MAXN = 100000;
int n, a[MAXN | 1], b[MAXN | 1], dp[MAXN | 1], bit[MAXN | 1];
struct Range {
  int l, r, res;
  Range() : l(0), r(0), res(0) {}
  Range(int _l, int _r) : l(_l), r(_r) {}
  friend bool operator< (const Range &lhs, const Range &rhs) {
    return lhs.l < rhs.l || (lhs.l == rhs.l && lhs.r < rhs.r);
  }
} range[MAXN | 1], tm[MAXN | 1];
inline bool comp(const Range &lhs, const Range &rhs) {
  return lhs.r < rhs.r;
}
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 modify(int x, int y) {
  if (x <= 0) x = 1;
  while (x <= n) {
    bit[x] = std::max(bit[x], y);
    x += x & (-x);
  } 
}
int query(int x) {
  int res = 0xcfcfcfcf;
  // printf("res=%d\n", res);
  while (x > 0) {
    res = std::max(res, bit[x]);
    x -= x & (-x);
  }
  return res;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    b[i] = read();
  }
  for (int i = 1; i <= n; ++i) {
    range[i].l = a[i] + 1;
    range[i].r = n - b[i];
  }
  std::sort(range + 1, range + 1 + n);
  int tot = 0;
  for (int i = 1; i <= n; ++i) {
    if (range[i].l > range[i].r) continue;
    if (range[i].l != range[i - 1].l || range[i].r != range[i - 1].r) {
      tm[++tot].l = range[i].l;
      tm[tot].r = range[i].r;
      tm[tot].res = 1;
    } else {
      tm[tot].res += 1;
      if (tm[tot].res > tm[tot].r - tm[tot].l + 1) tm[tot].res = tm[tot].r - tm[tot].l + 1;
    }
  }
  std::sort(tm + 1, tm + 1 + tot, comp);
  memset(bit, 0xcf, sizeof(bit));
  dp[tm[1].r] = tm[1].res;
  modify(tm[1].r, tm[1].res);
  for (int i = 2; i <= tot; ++i) {
    dp[tm[i].r] =  std::max(query(tm[i].l - 1), 0) + tm[i].res;
    modify(tm[i].r, dp[tm[i].r]);
  }
  printf("%d\n", n - query(tm[tot].r));
  return 0;
}