Luogu2418 yyy loves OI IV

线段树优化 DP。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

const int MAXN = 1e6;

int n, m;
int a[MAXN | 1], tot1[MAXN | 1], tot2[MAXN | 1], min1[MAXN | 1], min2[MAXN | 1];
int dp[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;
}

namespace SegTree {
  struct Node {
    int minv;
    Node *ch[2];
    Node() : minv(0) {
      ch[0] = ch[1] = NULL;
    }
  } *root;
  void push_up(Node *o) {
    o -> minv = std::min(o -> ch[0] -> minv, o -> ch[1] -> minv);
  }
  void build(Node *&o, int l, int r) {
    o = new Node;
    if (l == r) {
      o -> minv = 1e9;
      return;
    }
    int mid = (l + r) >> 1;
    build(o -> ch[0], l, mid);
    build(o -> ch[1], mid + 1, r);
    push_up(o);
  }
  void modify(Node *o, int l, int r, int pos, int v) {
    if (l == r) {
      o -> minv = std::min(o -> minv, v);
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(o -> ch[0], l, mid, pos, v);
    else modify(o -> ch[1], mid + 1, r, pos, v);
    push_up(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;
    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;
  }
}

using namespace SegTree;

int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    tot1[i] = tot1[i - 1];
    tot2[i] = tot2[i - 1];
    if (a[i] == 1) ++tot1[i];
    else ++tot2[i];
  }
  memset(min1, 0x3f, sizeof(min1));
  memset(min2, 0x3f, sizeof(min2));
  memset(dp, 0x3f, sizeof(dp));
  build(root, 0, 2 * n + 2 * m);
  modify(root, 0, 2 * n +  2 * m, n + m, 0);
  for (int i = 1; i <= n; ++i) {
    dp[i] = std::min(dp[i], min1[tot1[i]] + 1);
    dp[i] = std::min(dp[i], min2[tot2[i]] + 1);
    dp[i] = std::min(dp[i], query(root, 1, 2 * n + 2 * m, tot1[i] - tot2[i] - m + n + m, tot1[i] - tot2[i] + m + n + m) + 1);
    modify(root, 0, 2 * n + 2 * m, tot1[i] - tot2[i] + n + m, dp[i]);
    min1[tot1[i]] = std::min(min1[tot1[i]], dp[i]);
    min2[tot2[i]] = std::min(min2[tot2[i]], dp[i]);
  }
  printf("%d\n", dp[n]);
  return 0;
}
最后修改:2019 年 10 月 10 日 02 : 17 PM

发表评论