Dividing the Path

友情链接：POJ - 2373

Farmer John’s cows have discovered that the clover growing along the ridge of the hill in his field is particularly good. To keep the clover watered, Farmer John is installing water sprinklers along the ridge of the hill.

To make installation easier, each sprinkler head must be installed along the ridge of the hill (which we can think of as a one-dimensional number line of length L ($1\leq L\leq1,000,000$); L is even).

Each sprinkler waters the ground along the ridge for some distance in both directions. Each spray radius is an integer in the range A..B ($1 \leq A \leq B \leq 1000$). Farmer John needs to water the entire ridge in a manner that covers each location on the ridge by exactly one sprinkler head. Furthermore, FJ will not water past the end of the ridge in either direction.

Each of Farmer John’s N ($1\leq N\leq 1000$) cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval (S,E). Each of the cow’s preferred ranges must be watered by a single sprinkler, which might or might not spray beyond the given range.

Find the minimum number of sprinklers required to water the entire ridge without overlap.

Input

* Line 1: Two space-separated integers: N and L

* Line 2: Two space-separated integers: A and B

* Lines 3..N+2: Each line contains two integers, S and E ($0\leq S < E\leq L$) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge and so are in the range $0..L$.

Output

* Line 1: The minimum number of sprinklers required. If it is not possible to design a sprinkler head configuration for Farmer John, output -1.

Sample Input

1
2
3
4
2 8
1 2
6 7
3 6

Sample Output

1
3

Hint

INPUT DETAILS: 

1
2
3
4
            |-----c2----|-c1|       cows' preferred ranges
|---1---|-------2-------|---3---|   sprinklers
+---+---+---+---+---+---+---+---+
0   1   2   3   4   5   6   7   8

The sprinklers are not considered to be overlapping at 2 and 6.

题意：

有一条长为 $L$ 的线段，线段上的点从 $0$ 到 $L$ 编号，线段上有 $n$ 头🐂，每头🐂有自己的活动范围为$(S, L)$ ，现在你有一种喷洒半径为 $[A, B]$ 的喷头，即每一个这种喷头可在该区间内选定一个值作为喷洒半径，现在让你去线段上放置喷头，每个点必须且只能被一个喷头覆盖，喷头的喷洒范围不能超过线段的两端，每一头🐂的活动范围至少要被一个喷头完全覆盖，请问最少需要放置多少个喷头？如果不可能，输出-1

解题方案：

本渣渣想了半天想不到按照什么去 dp， 看了提示是按照覆盖至某一个点，然后自己又想了半天，WA了无数次，才得以AC。

设 $dp(x)$ 为，左端点为 $0$，右端点覆盖至 $x$ 时的最少放置数，那么我们就可以知道，以 x 为右端点，喷头的放置位置为 $[x - B, x - A]$，这是显然的，另外一个不好想到的点是，$x$ 不能处于任意一头🐂的活动范围内，为啥？注意到条件，每个点必须且只能被覆盖一次（端点不算），若 $x$ 处于某头牛的活动范围内，则这头牛的活动范围就不能被某一喷头覆盖了，必然至少两个喷头所分割。同理，该喷头的左端点理论上也是要满足这个条件的，但其实处理时左端点无需加此判断（看代码思考）。

该喷头的左端点范围是 $[x - 2B, x - 2A]$ 那么，状态转移方程就是

这里涉及到一个优化，即若我们暴力的去区间 $[x - 2B, x - 2A]$ 里找最小的 $dp(i)$ 的话，肯定是会超时的（注意数据范围），那么就要用的单调队列进行优化（上一篇博客，此处不细讲）

（一个很讨厌的事(╯▔皿▔)╯，POJ的老年评测姬不支持万能头，记得把头文件改下）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Dividing the Path
 * POJ-2373
 */

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;

struct node {
  int l, r;

  bool operator<(const node &t) const {
    if (l == t.l) {
      return r < t.r;
    } else {
      return l < t.l;
    }
  }
} a[1000 + 10];

int dp[maxn];
bool iscow[maxn];

int main() {
  int n, l, A, B;
  memset(dp, inf, sizeof(dp));
  scanf("%d%d", &n, &l);
  scanf("%d%d", &A, &B);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a[i].l, &a[i].r);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {  // 把牛的活动范围标一下，注意端点，容易出错
    int tl = max(a[i].l + 1, a[i - 1].r);
    for (int j = tl; j < a[i].r; j++) {
      iscow[j] = true;
    }
  }
  deque<int> q;
  q.push_back(0);
  dp[0] = 0;
  for (int j = 2 * A; j <= l; j += 2) {
    // 注意 t2 一定要先比 t1 入队！
    int t2 = j - 2 * A - 1;
    while (!q.empty() && dp[q.back()] >= dp[t2]) {
      q.pop_back();
    }
    q.push_back(t2);
    int t1 = j - 2 * A;
    while (!q.empty() && dp[q.back()] >= dp[t1]) {
      q.pop_back();
    }
    q.push_back(t1);
    if (!iscow[j]) {
      while (!q.empty() && q.front() < j - 2 * B) {
        q.pop_front();
      }
      if (q.empty()) {
        break;
      }
      dp[j] = dp[q.front()] + 1;
    }
  }
  if (dp[l] >= inf) {
    dp[l] = -1;
  }
  printf("%d\n", dp[l]);
  return 0;
}

继续刷 dp。(ノ｀Д)ノ