POJ2373 动态规划

单调队列优化的 dp。首先我们先进行预处理，将可以合并的区间合并到一起，这个可以在 $O(n \lg n)$ 的时间内完成。方法是按照 $x$ 排序，然后找相邻的两个区间 $(a, b)$ 和 $(c, d)$ 是否满足 $a < d$ 并且 $b > c$，注意这里必须严格大于才行，因为这里的区间都是开区间，如果存在 $b = c$ 这样的情况，那么 b 这个点就可以分割。

然后进行动态规划转移，令 $dp[i]$ 为前 $i$ 个区间可以划分的最小区间数目，那么就有：

$$dp[i]=\min\{dp[i-2k]\}+1,  A \leq k \leq B$$

如果不存在这样的 $k$ 值，或者 $i$ 是在某个区间内，那么 $dp[i]$ 就为 $\infty$，注意初始化 $dp[0] = 1, dp[1] = \infty$。

运用类似多重背包的方法将 $i$ 划分成 $2$ 的一个剩余类，也就是说我们可以对上式进行变形，变成如下的形式：

$$dp[mod+2j]=\min\{dp[mod+2k]\}+1, A \leq j-k \leq B$$

这里 $dp[mod+2j]$ 是个仅关于 $j$ 的函数，可以用单调队列维护一定区间的最值，最后问题得到解决。

注意这题的一些细节，首先当 $L$ 为奇数的时候 $dp[L]$ 与 $dp[1]$ 属于同一个剩余类，那么 $dp[L]$ 就为 $\infty$，所以直接可以输出 $-1$。其次，对于判断 $i$ 是否在区间内，可以用一个指针 $p$ 动态向后移动的方式来判断，如果第 $p$ 个区间的右边界小等于 $i$，那么 $p$ 就右移，知道 $p$ 等于 $n$ 或者右边界大于 $i$ 为止，这时候判断第 $p$ 个区间的左边界是否比 $i$ 小，如果左边界小于 $i$，那么 $dp[i]$ 就是 $\infty$。最后，如果 $dp[L]$ 等于 $\infty$ 记得输出 $-1$。

这里还有一个很好的技巧，在队列中加一个哨兵 $\infty$，它的 $id$ 也为 $\infty$，这样可以处理如果 $i < A$ 的情况，当然也可以直接预处理出对所有的 $i < A$ 都有 $dp[i] = \infty$，注意这里枚举和 $0$ 的同剩余类的元素要从 $2$ 开始循环！

我的代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

const int MAX = 1001000;
const int oo = 0x3f3f3f3f;
int dp[MAX];

struct Seg {
  int x, y;
  Seg(int x = 0, int y = 0) : x(x), y(y) {}
  bool operator<(const Seg& seg) const { return x < seg.x; }
} seg[1100];
int q[MAX], id[MAX], f, b;

int merge(int n) {
  int top = 0;
  sort(seg, seg + n);
  int l = seg[0].x, r = seg[0].y;
  for (int i = 1; i < n; i++) {
    if (seg[i].x < r) {
      r = max(r, seg[i].y);
    } else {
      seg[top++] = Seg(l, r);
      l = seg[i].x;
      r = seg[i].y;
    }
  }
  seg[top++] = Seg(l, r);
  return top;
}

int main() {
  int n, L, l, r, p;
  scanf("%d%d", &n, &L);
  if (L & 1) {
    printf("%d\n", -1);
    return 0;
  }
  scanf("%d%d", &l, &r);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &seg[i].x, &seg[i].y);
  }
  n = merge(n);
  l <<= 1;
  r <<= 1;
  dp[0] = 0;
  f = b = 0;
  p = 0;
  dp[0] = 0;
  for (int i = 2; i < l; i += 2) dp[i] = oo;
  // start with 2.
  for (int i = l; i <= L; i += 2) {
    while (f != b && i - id[f] > r) f++;
    while (f != b && q[b - 1] >= dp[i - l]) b--;
    id[b] = i - l;
    q[b++] = dp[i - l];
    while (p < n && seg[p].y <= i) p++;
    // if q[f] is oo, not to set dp[i] = q[f]+1. else dp[i]=q[f]+1;
    if (p < n && seg[p].x < i || q[f] == oo) dp[i] = oo;
  }
  // for(int i=0;i<=L;i+=2)printf("%d ",dp[i]==oo?-1:dp[i]);puts("");
  printf("%d\n", dp[L] == oo ? -1 : dp[L]);
  return 0;
}